Submission #261004

#	Time	Username	Problem	Language	Result	Execution time	Memory
261004		atoiz	Palindromes (APIO14_palindrome)	C++14	100 / 100	32 ms	35160 KiB

palindrome

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN = 300007;
int link[MAXN], nxt[MAXN][26], len[MAXN], val[MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	string S;
	cin >> S;

	len[1] = -1, len[2] = 0;
	link[2] = 1;
	int u = 2, cnt = 2;
	int N = ((int) S.size());
	S = "-" + S;

	for (int i = 1; i <= N; ++i) {
		int c = (int) (S[i] - 'a');
		while (S[i] != S[i - len[u] - 1]) u = link[u];
		if (!nxt[u][c]) {
			nxt[u][c] = ++cnt;
			// cout << u << " -> " << nxt[u][c] << ": " << char(c + 'a') << endl;
			len[nxt[u][c]] = len[u] + 2;

			int v;
			for (v = link[u]; v && S[i] != S[i - len[v] - 1]; v = link[v]);
			if (v == 0) link[nxt[u][c]] = 2;
			else link[nxt[u][c]] = nxt[v][c];
		}
		u = nxt[u][c];
		++val[u];
	}

	int64_t ans = 0;
	for (int u = cnt; u > 2; --u) {
		// cout << u << ": " << len[u] << ' ' << val[u] << " -> " << link[u] << endl;
		if (link[u]) val[link[u]] += val[u];
		ans = max(ans, (int64_t) val[u] * len[u]);
	}
	cout << ans << endl;
}

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