Submission #243618

#TimeUsernameProblemLanguageResultExecution timeMemory
243618islingrPalindromes (APIO14_palindrome)C++14
100 / 100
34 ms35068 KiB
#include <iostream> using namespace std; const int N = 5 << 16, A = 26; int link[N], len[N], nxt[N][A], occ[N], cnt = 2, lst = 2; char s[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> s; len[1] = -1; link[1] = 1; len[2] = -0; link[2] = 1; for (int i = 0; s[i]; ++i) { int cur = lst, a = s[i] - 'a'; while (s[i - len[cur] - 1] != s[i]) cur = link[cur]; int &tmp = nxt[cur][a]; if (!tmp) { tmp = ++cnt; len[tmp] = len[cur] + 2; if (cur != 1) { cur = link[cur]; while (s[i - len[cur] - 1] != s[i]) cur = link[cur]; link[tmp] = nxt[cur][a]; } else link[tmp] = 2; } lst = tmp; ++occ[lst]; } long long ans = 0; for (int i = cnt; i > 2; --i) { occ[link[i]] += occ[i]; ans = max(ans, 1ll * occ[i] * len[i]); } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...