Submission #168095

#TimeUsernameProblemLanguageResultExecution timeMemory
168095HungAnhGoldIBO2020Palindromes (APIO14_palindrome)C++14
47 / 100
574 ms102192 KiB
/* abacaba */ #include<bits/stdc++.h> #define int long long #define hash hash1 using namespace std; const int N=3e5+14; const int mod=3000003529; const int base=211; int hash[N],rev_hash[N],mul[N],max1=1,sum[N]; map<int,int> cnt; bool used[N]; int gethash(int l,int r){ return ((hash[r]-hash[l-1]*mul[r-l+1])%mod+mod)%mod; } int gethash_rev(int l,int r){ return ((rev_hash[l]-rev_hash[r+1]*mul[r-l+1])%mod+mod)%mod; } struct node{ int nxt[26],len,suf; }; node Eer[N]; int sz=0,lst; string s; void add(int idx){ // cout<<idx<<" BEGIN"<<endl; int cha=(s[idx]-'a'); while(idx-Eer[lst].len-1<0||s[idx]!=s[idx-Eer[lst].len-1]){ lst=Eer[lst].suf; } if(!Eer[lst].nxt[cha]){ sz++; Eer[lst].nxt[cha]=sz; Eer[sz].len=Eer[lst].len+2; if(Eer[sz].len!=1){ int sf=Eer[lst].suf; while(idx-Eer[sf].len-1<0||s[idx]!=s[idx-Eer[sf].len-1]){ sf=Eer[sf].suf; } Eer[sz].suf=Eer[sf].nxt[cha]; } else{ Eer[sz].suf=2; } } lst=Eer[lst].nxt[cha]; return; } void build(string s1){ sz=2; Eer[1].len=-1; Eer[1].suf=0; Eer[2].len=0; Eer[2].suf=1; lst=2; s=s1; for(int i=0;i<s.size();i++){ add(i); } } void dfs(int x,int val){ assert(!used[x]); used[x]=true; sum[x]=cnt[val]; for(int i=0;i<26;i++){ if(Eer[x].nxt[i]){ if(x==1){ dfs(Eer[x].nxt[i],i+1); } else{ dfs(Eer[x].nxt[i],(i+1 + val*base + (i+1)*mul[Eer[x].len+1])%mod); } sum[x]+=sum[Eer[x].nxt[i]]; } } max1=max(max1,Eer[x].len * sum[x]); } signed main(){ ios::sync_with_stdio(0); cin.tie(0); string s1; cin>>s1; build(s1); int n=s1.size(),i,j,k,l; s1=" "+s1; mul[0]=1; for(i=1;i<=n;i++){ hash[i]=(hash[i-1]*base+(s1[i]-'a'+1))%mod; mul[i]=(mul[i-1]*base)%mod; } for(i=n;i>0;i--){ rev_hash[i]=(rev_hash[i+1]*base+(s1[i]-'a'+1))%mod; } for(i=1;i<=n;i++){ k=0; l=min(i-1,n-i); while(k<l){ j=(k+l+1)>>1; if(gethash(i-j,i+j)==gethash_rev(i-j,i+j)){ k=j; } else{ l=j-1; } } cnt[gethash(i-k,i+k)]++; if(i<=n&&s1[i]==s1[i+1]){ k=0; l=min(i-1,n-i-1); while(k<l){ j=(k+l+1)>>1; if(gethash(i-j,i+1+j)==gethash_rev(i-j,i+1+j)){ k=j; } else{ l=j-1; } } cnt[gethash(i-k,i+1+k)]++; } } dfs(1,0); dfs(2,0); cout<<max1; }

Compilation message (stderr)

palindrome.cpp: In function 'void build(std::__cxx11::string)':
palindrome.cpp:58: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...