제출 #654802

#제출 시각아이디문제언어결과실행 시간메모리
654802NeroZein회문 (APIO14_palindrome)C++14
100 / 100
26 ms35208 KiB
#include <bits/stdc++.h> using namespace std; const int N = 3e5+10; string s; int num,suff; struct node{ int next[26]; int len,num,sufflink; }tree[N]; inline void ini(){ num = suff = 2; tree[1].len = -1;tree[1].sufflink = 1; tree[2].len = 0;tree[2].sufflink = 1; } inline void add(int pos){ int cur = suff, curlen = 0; int let = s[pos]-'a'; while (true){ curlen = tree[cur].len; if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]) break; cur = tree[cur].sufflink; } if (tree[cur].next[let]){ suff = tree[cur].next[let]; tree[tree[cur].next[let]].num++; return; } suff = ++num; tree[cur].next[let] = num; tree[num].len = tree[cur].len+2; tree[tree[cur].next[let]].num++; if (tree[num].len == 1){ tree[num].sufflink = 2; return; } while(true){ cur = tree[cur].sufflink; curlen = tree[cur].len; if (pos-1-curlen >= 0 && s[pos-1-curlen] == s[pos]){ tree[num].sufflink = tree[cur].next[let]; break; } } } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin>>s;int n = s.size(); ini(); for(int i=0;i<n;++i) add(i); for(int i=n+3;~i;--i) tree[tree[i].sufflink].num += tree[i].num; long long ans = 0; for(int i=3;i<n+3;i++) ans = max(ans, 1LL*tree[i].num*tree[i].len); 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...