Submission #13190

#TimeUsernameProblemLanguageResultExecution timeMemory
13190baneling100Palindromes (APIO14_palindrome)C++98
73 / 100
1000 ms44152 KiB
#include <stdio.h> #include <algorithm> #include <string.h> #define N_MAX 300000 using namespace std; pair <int,int> PAL[4*N_MAX]; int N, N_, MA[2*N_MAX], SA[2*N_MAX], LCP[2*N_MAX], STK[2][2*N_MAX], Top; int Rank[4*N_MAX], Rtemp[4*N_MAX], Len, Loc[2*N_MAX], Cnt, POS1[4*N_MAX], POS2[4*N_MAX]; long long Ans; char S[2*N_MAX+1], S_[N_MAX+2]; bool comp1(int p, int q) {return S[p]<S[q];}; bool comp2(int p, int q) {return Rank[p]<Rank[q] || (Rank[p]==Rank[q] && Rank[p+Len]<Rank[q+Len]);}; void input(void) { int i; scanf("%s",&S_[1]); N_=strlen(&S_[1]); for(i=1 ; i<=N_ ; i++) { S[2*i-1]=S_[i]; S[2*i ]='#'; } S[2*N_]=NULL; N=2*N_-1; } void manacher(void) { int i, j=0; for(i=1 ; i<=N ; i++) { i<=j+MA[j] ? MA[i]=min(j+MA[j]-i,MA[2*j-i]) : MA[i]=0; while(i+MA[i]+1<=N && S[i-MA[i]-1]==S[i+MA[i]+1]) MA[i]++; if(j+MA[j]<i+MA[i]) j=i; } } void suffixArray(void) { int i; for(i=1 ; i<=N ; i++) SA[i]=i; sort(SA+1,SA+N+1,comp1); for(i=1 ; i<=N ; i++) { if(S[SA[i]]==S[SA[i-1]]) Rank[SA[i]]=Rank[SA[i-1]]; else Rank[SA[i]]=i; } for(Len=1 ; Len<N ; Len<<=1) { sort(SA+1,SA+N+1,comp2); for(i=1 ; i<=N ; i++) { if(Rank[SA[i]]>Rank[SA[i-1]] || (Rank[SA[i]]==Rank[SA[i-1]] && Rank[SA[i]+Len]>Rank[SA[i-1]+Len])) Rtemp[SA[i]]=i; else Rtemp[SA[i]]=Rtemp[SA[i-1]]; } for(i=1 ; i<=N ; i++) Rank[i]=Rtemp[i]; } } void longestCommonPrefix(void) { int i; for(i=1 ; i<=N ; i++) Loc[SA[i]]=i; for(i=1 ; i<=N ; i++) { if(LCP[Loc[i-1]]) LCP[Loc[i]]=LCP[Loc[i-1]]-1; while(S[i+LCP[Loc[i]]]==S[SA[Loc[i]-1]+LCP[Loc[i]]]) LCP[Loc[i]]++; } } void calculate(void) { int i, j=0, p; for(i=1 ; i<=N ; i++) while(j+1<=i+MA[i]) { j++; PAL[++Cnt]=make_pair(Loc[2*i-j],2*(j-i)+1); } sort(PAL+1,PAL+Cnt+1); j=1; STK[0][Top]=-1; for(i=1 ; i<=N ; i++) { while(STK[0][Top]>=LCP[i]) Top--; STK[0][++Top]=LCP[i]; STK[1][ Top]=i; while(j<=Cnt && PAL[j].first==i) { p=lower_bound(STK[0]+1,STK[0]+Top+1,PAL[j].second)-STK[0]-1; POS1[j]=STK[1][p]; j++; } } Top=0; j=Cnt; for(i=N ; i>=1 ; i--) { while(STK[0][Top]>=LCP[i+1]) Top--; STK[0][++Top]=LCP[i+1]; STK[1][ Top]=i; while(j>=1 && PAL[j].first==i) { p=lower_bound(STK[0]+1,STK[0]+Top+1,PAL[j].second)-STK[0]-1; POS2[j]=STK[1][p]; j--; } } for(i=1 ; i<=Cnt ; i++) { if(S[SA[PAL[i].first]]=='#') { if(Ans<(long long)(PAL[i].second/2)*(POS2[i]-POS1[i]+1)) Ans=(long long)(PAL[i].second/2)*(POS2[i]-POS1[i]+1); } else if(Ans<(long long)(PAL[i].second/2+1)*(POS2[i]-POS1[i]+1)) Ans=(long long)(PAL[i].second/2+1)*(POS2[i]-POS1[i]+1); } } int main(void) { input(); manacher(); suffixArray(); longestCommonPrefix(); calculate(); printf("%lld",Ans); 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...