#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;
int p1[M],p2[M],st1[M],st2[M];
char a[M],s[M*2],b[M*2];
struct data
{
int x,y,p;
bool operator<(const data&r)const{
if(x==r.x) return y<r.y;
return x<r.x;
}
}L[M];
void Suffix_Array()
{
int i,j,k=1,cnt;
for(i=1;i<=n;i++) SA[0][i]=a[i]-'a'+1;
for(i=1;;i++)
{
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;
}
sort(L+1,L+n+1);
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 |
43572 KB |
Output is correct - answer is '7' |
| 2 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '4' |
| 3 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '9' |
| 4 |
Incorrect |
0 ms |
43572 KB |
Output isn't correct - expected '1', found '0' |
| 5 |
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 |
- |
