#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[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 time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
44152 KB |
Output is correct - answer is '7' |
| 2 |
Correct |
0 ms |
44152 KB |
Output is correct - answer is '4' |
| 3 |
Incorrect |
3 ms |
44152 KB |
Output isn't correct - expected '9', found '8' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
