#include<stdio.h>
#include<algorithm>
#include<string.h>
#define M 300010
using namespace std;
int dap,n,SA[20][M],arr[M],order[M],lcp[M],d[M*2],arr2[M*2],len[M],top,ch[30],cnt2[30];
int p1[M],p2[M],st1[M],st2[M],sor2[28][100010];
char a[M],s[M*2],b[M*2];
struct data
{
int x,y,p;
}L[M];
struct data2
{
int y,p;
}sor[28][100010];
void Suffix_Array()
{
int i,j,k=1,cnt,l,w,r;
for(i=1;i<=n;i++) ch[a[i]-'a'+1]=1;
for(i=1;i<=26;i++) ch[i]+=ch[i-1];
for(i=1;i<=n;i++) SA[0][i]=ch[a[i]-'a'+1];
for(i=1;;i++)
{
memset(ch,0,sizeof ch); w=0;
if(k>n-1) break;
for(j=1;j<=n;j++)
{
L[j].x=SA[i-1][j];
if(j+k<=n) L[j].y=SA[i-1][j+k];
else L[j].y=-1;
L[j].p=j;
}
for(j=1;j<=n;j++){ch[L[j].x+1]++; sor[L[j].x+1][ch[L[j].x+1]].y=L[j].y+1; sor[L[j].x+1][ch[L[j].x+1]].p=L[j].p;}
for(j=0;j<=27;j++){
memset(cnt2,0,sizeof cnt2);
for(l=1;l<=ch[j];l++){cnt2[sor[j][l].y]++; sor2[sor[j][l].y][cnt2[sor[j][l].y]]=sor[j][l].p;}
for(l=0;l<=27;l++){
for(r=1;r<=cnt2[l];r++){
w++; L[w].x=j-1; L[w].y=l-1; L[w].p=sor2[l][r];
}
}
}
cnt=0;
for(j=1;j<=n;j++)
{
if(L[j].x!=L[j-1].x) SA[i][L[j].p]=++cnt;
else if(L[j].y!=L[j-1].y) SA[i][L[j].p]=++cnt;
else SA[i][L[j].p]=cnt;
}
k*=2;
}
for(j=1;j<=n;j++) arr[j]=SA[i-1][j];
}
void LCP()
{
int i,j,k=0;
for(i=1;i<=n;i++) order[arr[i]]=i;
for(i=1;i<=n;i++){
if(arr[i]==1){k=0; continue;}
if(k>0 && a[order[arr[i]-1]+k-1]!=a[order[arr[i]]+k-1]){k--; lcp[arr[i]]=k; continue;}
for(j=k;j<=n;j++){
if(order[arr[i]-1]+j>n || order[arr[i]]+j>n || a[order[arr[i]-1]+j]!=a[order[arr[i]]+j]) break;
}
k=j;
lcp[arr[i]]=k;
}
}
void Manacher()
{
int i,r=0,p=0;
for(i=1;i<=n*2;i++){
if(r<i) d[i]=0;
else d[i]=min(d[2*p-i],r-i);
while(b[i+d[i]+1]==b[i-d[i]-1]) d[i]++;
if(r<d[i]+i) r=d[i]+i;
}
}
void solve()
{
int i,big=0,pos,*q;
for(i=1;i<=n*2;i++) arr2[(i-d[i])/2+1]=i;
for(i=1;i<=n;i++){
if(big<arr2[i]) big=arr2[i];
if(big%2==1) len[arr[i]]=((big/2+1)-i)*2+1;
else len[arr[i]]=(big/2-i)*2+2;
}
st1[0]=-1;
for(i=1;i<=n;i++){
while(st1[top]>=lcp[i]) top--;
top++; st1[top]=lcp[i]; st2[top]=i;
q=lower_bound(st1+1,st1+top+1,len[i]); pos=q-st1;
p1[i]=st2[pos-1];
}
top=0;
for(i=n;i>=1;i--){
while(st1[top]>=lcp[i+1]) top--;
top++; st1[top]=lcp[i+1]; st2[top]=i;
q=lower_bound(st1+1,st1+top+1,len[i]); pos=q-st1;
p2[i]=st2[pos-1];
}
for(i=1;i<=n;i++){
if(dap<len[i]*(p2[i]-p1[i]+1)) dap=len[i]*(p2[i]-p1[i]+1);
}
}
int main()
{
int i;
scanf("%s",a);
n=strlen(a);
for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
for(i=1;i<=n*2;i++){
if(i%2==1) b[i]=a[i/2+1];
else b[i]='#';
}
Suffix_Array();
LCP();
Manacher();
solve();
printf("%d",dap);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '7' |
| 2 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '4' |
| 3 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '9' |
| 4 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '1' |
| 5 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '1' |
| 6 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '2' |
| 7 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '3' |
| 8 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '3' |
| 9 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '15' |
| 10 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '24' |
| 11 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '10' |
| 12 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '24' |
| 13 |
Correct |
0 ms |
76384 KB |
Output is correct - answer is '25' |
| 14 |
Incorrect |
0 ms |
76384 KB |
Output isn't correct - expected '28', found '25' |
| 15 |
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 |
- |
