제출 #106250

#제출 시각아이디문제언어결과실행 시간메모리
106250ToMo01회문 (APIO14_palindrome)C++17
100 / 100
57 ms36088 KiB
/*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; }
#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...