Submission #31178

#TimeUsernameProblemLanguageResultExecution timeMemory
31178tatatanPalindromes (APIO14_palindrome)C++11
100 / 100
19 ms37912 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define pii pair<int,int> #define LL long long #define st first #define nd second #define endl '\n' using namespace std; const int N=3e5+5; int suff[N],len[N],lz[N],nxt[N][26],cur,tt=3; LL ans; string s; stack<int> st; void add(int x) { while(s[x-len[cur]-1]!=s[x]) cur=suff[cur]; int y=s[x]-'a'; if(nxt[cur][y]) { cur=nxt[cur][y]; ++lz[cur]; return; } int nw=tt++; st.push(nw); ++lz[nw]; len[nw]=len[cur]+2; if(len[nw]==1) { suff[nw]=2; nxt[cur][y]=nw; cur=nw; return; } int tmp2=cur; cur=suff[cur]; while(s[x-len[cur]-1]!=s[x]) cur=suff[cur]; suff[nw]=nxt[cur][y]; cur=nw; nxt[tmp2][y]=cur; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>s; len[1]=-1; suff[1]=1; len[2]=0; suff[2]=1; cur=1; for(int i=0;i<s.size();++i) add(i); while(!st.empty()) { int x=st.top(); st.pop(); ans=max(ans,1LL*len[x]*lz[x]); lz[suff[x]]+=lz[x]; } cout<<ans<<endl; }

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<s.size();++i) 
               ^
#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...