#include<stdio.h>
#include<algorithm>
#include<string.h>
#define M 300010
using namespace std;
long long dap;
int n,SA[20][M],arr[M],order[M],lcp[M],d[M*2],arr2[M*2],len[M],top,ch[30];
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++) 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++)
{
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, p=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<(long long)len[i]*(long long)(p2[i]-p1[i]+1)) dap=(long long)len[i]*(long long)(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("%lld",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 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '1' |
5 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '1' |
6 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '2' |
7 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '3' |
8 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '3' |
9 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '15' |
10 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '24' |
11 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '10' |
12 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '24' |
13 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '25' |
14 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '28' |
15 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '2' |
16 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '1' |
17 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '15' |
18 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '18' |
19 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '1176' |
20 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '1225' |
21 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '136' |
22 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '45' |
23 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '2500' |
24 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '380' |
25 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '2304' |
26 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '110' |
27 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '93' |
28 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '729' |
29 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '132' |
30 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '7' |
31 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '8' |
32 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '64' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '124251' |
2 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '38226' |
3 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '249500' |
4 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '5778' |
5 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '247506' |
6 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '248004' |
7 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '973' |
8 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '123753' |
9 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '2346' |
10 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '53' |
11 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '52' |
12 |
Correct |
0 ms |
43572 KB |
Output is correct - answer is '976' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '12497500' |
2 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '6481800' |
3 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '25000000' |
4 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '17816841' |
5 |
Correct |
12 ms |
43572 KB |
Output is correct - answer is '9945' |
6 |
Correct |
4 ms |
43572 KB |
Output is correct - answer is '504100' |
7 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '1512930' |
8 |
Correct |
8 ms |
43572 KB |
Output is correct - answer is '413' |
9 |
Correct |
12 ms |
43572 KB |
Output is correct - answer is '428' |
10 |
Correct |
12 ms |
43572 KB |
Output is correct - answer is '7232' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
120 ms |
43572 KB |
Output is correct - answer is '1249925001' |
2 |
Correct |
168 ms |
43572 KB |
Output is correct - answer is '396337935' |
3 |
Correct |
132 ms |
43572 KB |
Output is correct - answer is '2500050000' |
4 |
Correct |
148 ms |
43572 KB |
Output is correct - answer is '1016525689' |
5 |
Correct |
180 ms |
43572 KB |
Output is correct - answer is '99645' |
6 |
Correct |
168 ms |
43572 KB |
Output is correct - answer is '78569380' |
7 |
Correct |
140 ms |
43572 KB |
Output is correct - answer is '82810000' |
8 |
Correct |
200 ms |
43572 KB |
Output is correct - answer is '3989' |
9 |
Correct |
184 ms |
43572 KB |
Output is correct - answer is '125529616' |
10 |
Correct |
184 ms |
43572 KB |
Output is correct - answer is '66664' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
436 ms |
43572 KB |
Output is correct - answer is '11250075000' |
2 |
Correct |
480 ms |
43572 KB |
Output is correct - answer is '894243195' |
3 |
Correct |
480 ms |
43572 KB |
Output is correct - answer is '22499400004' |
4 |
Correct |
428 ms |
43572 KB |
Output is correct - answer is '2958163321' |
5 |
Correct |
644 ms |
43572 KB |
Output is correct - answer is '298935' |
6 |
Correct |
524 ms |
43572 KB |
Output is correct - answer is '1210831209' |
7 |
Correct |
552 ms |
43572 KB |
Output is correct - answer is '303195156' |
8 |
Correct |
748 ms |
43572 KB |
Output is correct - answer is '11804' |
9 |
Correct |
728 ms |
43572 KB |
Output is correct - answer is '11813' |
10 |
Correct |
636 ms |
43572 KB |
Output is correct - answer is '262144' |
11 |
Correct |
488 ms |
43572 KB |
Output is correct - answer is '3750025000' |
12 |
Correct |
740 ms |
43572 KB |
Output is correct - answer is '184796836' |