Submission #34115

#TimeUsernameProblemLanguageResultExecution timeMemory
34115wan2000Palindromes (APIO14_palindrome)C++14
0 / 100
46 ms44796 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 3e5+111; int n; string s; struct node{ int next[26]; int len; ll num; int suflink; node(){ memset(next,255,sizeof(next)); } }; node Tree[N]; int num, suf; ll res; void initTree(){ num = suf = 2; Tree[1].len = -1; Tree[1].suflink = 1; Tree[2].len = 0; Tree[2].suflink = 1; } void addLetter(int p){ int cur = suf, curlen = 0; int x = s[p]-'a'; while(1){ curlen = Tree[cur].len; if(p-curlen-1>=0&&s[p-curlen-1]==s[p]) break; cur = Tree[cur].suflink; } if(Tree[cur].next[x]!=-1){ suf = Tree[cur].next[x]; Tree[Tree[cur].next[x]].num++; return; } suf = ++num; Tree[num].len = Tree[cur].len + 2; Tree[cur].next[x] = num; Tree[num].num = 1; if(Tree[num].len==1){ Tree[num].suflink = 2; return; } while(1){ cur = Tree[cur].suflink; curlen = Tree[cur].len; if(p-curlen-1>=0&&s[p-curlen-1]==s[p]){ Tree[num].suflink = Tree[cur].next[x]; break; } } return; } void DFS(int u){ Tree[Tree[u].suflink].num += Tree[u].num; for(int i = 0; i < 26; i++){ if(Tree[u].next[i]==-1) continue; DFS(Tree[u].next[i]); } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>s; n = s.size(); initTree(); for(int i = 0; i < n; i++){ addLetter(i); } DFS(1); DFS(2); for(int i = 3; i <= num; i++){ res = max(res,(ll)Tree[i].num*Tree[i].len); } cout<<res<<'\n'; return 0; }
#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...