Submission #106250

#	Time	Username	Problem	Language	Result	Execution time	Memory
106250		ToMo01	Palindromes (APIO14_palindrome)	C++17	100 / 100	57 ms	36088 KiB

palindrome

/*input
www
abacabaa
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 300005;
string s;
int link[N];
int val[N];
int len[N];
int adj[N][26];
int n, curNode = 1, treeSize = 1;

// 0 is even root, 1 is odd root
void build() {
	memset(adj, -1, sizeof adj);
	memset(link, -1, sizeof link);

	len[1] = -1;
	link[0] = 1, len[0] = 0;

	int tmp = 0;
	for(int i = 0; i < n; ++ i) {
		int ch = s[i] - 'a';
		for(tmp = curNode; ; tmp = link[tmp]) {
			int pos = i - len[tmp] - 1;
			if(pos >= 0 && s[pos] == s[i])
				break;
		}

		if(~adj[tmp][ch]) {
			curNode = adj[tmp][ch], ++ val[curNode]; continue;
		}

		adj[tmp][ch] = curNode = ++ treeSize;
		len[curNode] = len[tmp] + 2;

		if(len[curNode] == 1) {
			link[curNode] = 0;
		} else {
			while(1) {
				tmp = link[tmp];
				int pos = i - len[tmp] - 1;
				if(pos >= 0 && s[pos] == s[i])
					break;
			}
			link[curNode] = adj[tmp][ch];
		}
		++ val[curNode];
	}
}

int deg[N];

void bfs() {
	for(int i = 2; i <= treeSize; ++ i) ++ deg[link[i]];

	queue<int> q;
	for(int i = 2; i <= treeSize; ++ i) if(deg[i] == 0) q.push(i);

	while(!q.empty()) {
		int u = q.front(); q.pop();
		-- deg[link[u]], val[link[u]] += val[u];
		if(deg[link[u]] == 0) q.push(link[u]);
	}
}

int main(){
	iostream::sync_with_stdio(false); cin.tie(0);
	
	cin >> s;
	n = (int)s.size();
	build(), bfs();

	long long Ans = 1;
	for(int i = 2; i <= treeSize; ++ i) Ans = max(Ans, 1ll * len[i] * val[i]);
	cout << Ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27