Submission #1140713

#TimeUsernameProblemLanguageResultExecution timeMemory
114071312345678Palindromes (APIO14_palindrome)C++20
0 / 100
0 ms328 KiB
#include <bits/stdc++.h> using namespace std; struct node { int cnt, sz; node *nxt[26], *suf; vector<node*> g; node(int c, int s) { cnt=c; sz=s; g.clear(); for (int i=0; i<26; i++) nxt[i]=0; } }; typedef node* pnode; pnode rt=new node(0, -1), srt=new node(0, 0), t=rt; int n; long long ans; string s; void dfs(pnode x) { for (auto y:x->g) dfs(y), x->cnt+=y->cnt; ans=max(ans, ((long long)x->cnt)*x->sz); //cout<<"exit "<<x->sz<<' '<<x->cnt<<'\n'; } int main() { cin.tie(NULL)->sync_with_stdio(false); rt->suf=rt; srt->suf=rt; cin>>s; n=s.size(); for (int i=0; i<n; i++) { while (1) { if (i-1-t->sz>=0&&s[i-1-t->sz]==s[i]) break; t=t->suf; } if (t->nxt[s[i]-'a']) { t=t->nxt[s[i]]; t->cnt++; continue; } auto nw=new node(1, t->sz+2); t->nxt[s[i]-'a']=nw; if (nw->sz==1) { nw->suf=srt; nw->suf->g.push_back(nw); t=nw; continue; } while (1) { t=t->suf; if (i-1-t->sz>=0&&s[i-1-t->sz]==s[i]) { nw->suf=t->nxt[s[i]-'a']; nw->suf->g.push_back(nw); break; } } t=nw; } dfs(rt); dfs(srt); 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...