제출 #554992

#제출 시각아이디문제언어결과실행 시간메모리
554992sidon회문 (APIO14_palindrome)C++17
100 / 100
43 ms32292 KiB
#include <bits/stdc++.h> using namespace std; const int Z = 3e5+2; int n, sz[Z] {-1}, sLink[Z], cnt[Z], cur = 2, p = 1; map<char, int> c[Z]; string s; int main() { cin >> s; n = size(s); s = '_' + s; for(int i = 1; i <= n; ++i) { 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]); v = max(1, c[v][s[i]]); sz[cur] = sz[p] + 2; c[p][s[i]] = cur++; } ++cnt[p = c[p][s[i]]]; } long long res {}; for(int u = cur; u--; ) { res = max(res, 1LL * 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...