Submission #554982

#TimeUsernameProblemLanguageResultExecution timeMemory
554982sidonPalindromes (APIO14_palindrome)C++17
68 / 100
41 ms33772 KiB
#include <bits/stdc++.h> using namespace std; using i64 = int64_t; const int Z = 3e5+2, B = 26; int sz[Z] = {-1}, sLink[Z], cnt[Z], cur = 2, p = 1; map<int, int> c[Z]; int n, __s[Z] {-1}, *s = __s; string _s; int main() { ios::sync_with_stdio(0), cin.tie(0); cin >> _s; n = _s.size(); for(int i = 0; i < n; ++i) { s[i] = _s[i] - 'a'; for(; s[i-sz[p]-1] != s[i]; p = sLink[p]); if(!c[p][s[i]]) { int &v = (sLink[cur] = sLink[p]); for(; s[i-sz[v]-1] != s[i]; v = sLink[v]); sz[cur] = sz[p] + 2; c[p][s[i]] = cur; v = sz[v] + 2 < sz[cur] ? c[v][s[i]] : 1; cur++; } ++cnt[p = c[p][s[i]]]; } i64 res {}; for(int u = cur; u--; ) { res = max(res, i64(cnt[u]) * sz[u]); cnt[sLink[u]] += cnt[u]; } cout << res; }
#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...