#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define MAXN 300005
typedef long long lld;
int N;
int R[MAXN],SA[MAXN],pos[MAXN],lcp[MAXN],P[MAXN][19],Q[MAXN][19];
lld ans;
char A[MAXN];
void Manachers()
{
int r = 0, p = 0;
for (int i=1;i<=N;i++){
if (i <= r) R[i] = min(R[2*p-i],r-i);
else R[i] = 0;
while (i > R[i] && A[i-R[i]-1] == A[i+R[i]+1]) R[i]++;
if (r < i+R[i]) r = i+R[i], p = i;
}
}
void SuffixArray()
{
int i,j,k;
int m = 27;
vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0);
for (i=1;i<=N;i++) cnt[x[i] = (A[i]=='#')?27:A[i]-'a'+1]++;
for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
for (i=N;i;i--) SA[cnt[x[i]]--] = i;
for (int len=1,p=1;p<N;len<<=1,m=p){
for (p=0,i=N-len;++i<=N;) y[++p] = i;
for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
for (i=0;i<=m;i++) cnt[i] = 0;
for (i=1;i<=N;i++) cnt[x[y[i]]]++;
for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i];
swap(x,y); p = 1; x[SA[1]] = 1;
for (i=1;i<N;i++)
x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
}
}
void LCP()
{
int i,j,k=0;
vector <int> rank(N+1,0);
for (i=1;i<=N;i++) rank[SA[i]] = i;
for (i=1;i<=N;lcp[rank[i++]]=k)
for (k?k--:0,j=SA[rank[i]-1];A[i+k]==A[j+k];k++);
for (i=2;i<=N;i++) P[i][0] = Q[i][0] = lcp[i];
for (i=2;i<=N;i++){
for (j=0;j<18;j++){
P[i][j+1] = (i+(1<<j)<=N?min(P[i][j],P[i+(1<<j)][j]):0);
Q[i][j+1] = (i-(1<<j)>0?min(Q[i][j],Q[i-(1<<j)][j]):0);
}
}
}
void proc(int a,int b)
{
int i;
int len=b-a+1, cnt=1;
a = pos[a];
int p=a+1, q=a;
for (i=19;i--;){
if (Q[q][i] >= len) q -= (1<<i), cnt += (1<<i);
if (P[p][i] >= len) p += (1<<i), cnt += (1<<i);
}
ans = max(ans,(lld)len*cnt);
}
int main()
{
int i,j;
scanf("%s",A+1); N = strlen(A+1);
SuffixArray(); LCP();
for (i=1;i<=N;i++) pos[SA[i]] = i;
for (i=1;i<=N;i++){
for (j=0;j<i&&i+j<=N&&A[i-j]==A[i+j];j++){
proc(i-j,i+j);
}
}
for (i=1;i<N;i++) if (A[i] == A[i+1]){
for (j=0;j<i&&i+j+1<=N&&A[i-j]==A[i+j+1];j++){
proc(i-j,i+j+1);
}
}
printf("%lld\n",ans);
/*for (i=N;i;i--) A[i+i-1] = A[i]; N = N+N-1;
for (i=2;i<N;i+=2) A[i] = '#';
Manachers();
for (i=1;i<=N;i++){
int l = i-R[i];
}*/
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '7' |
2 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '4' |
3 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '9' |
4 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '1' |
5 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '1' |
6 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '2' |
7 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '3' |
8 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '3' |
9 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '15' |
10 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '24' |
11 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '10' |
12 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '24' |
13 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '25' |
14 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '28' |
15 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '2' |
16 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '1' |
17 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '15' |
18 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '18' |
19 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '1176' |
20 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '1225' |
21 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '136' |
22 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '45' |
23 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '2500' |
24 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '380' |
25 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '2304' |
26 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '110' |
27 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '93' |
28 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '729' |
29 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '132' |
30 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '7' |
31 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '8' |
32 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '64' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
50752 KB |
Output is correct - answer is '124251' |
2 |
Correct |
8 ms |
50752 KB |
Output is correct - answer is '38226' |
3 |
Correct |
52 ms |
50752 KB |
Output is correct - answer is '249500' |
4 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '5778' |
5 |
Correct |
48 ms |
50752 KB |
Output is correct - answer is '247506' |
6 |
Correct |
48 ms |
50752 KB |
Output is correct - answer is '248004' |
7 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '973' |
8 |
Correct |
20 ms |
50752 KB |
Output is correct - answer is '123753' |
9 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '2346' |
10 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '53' |
11 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '52' |
12 |
Correct |
0 ms |
50752 KB |
Output is correct - answer is '976' |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1000 ms |
50748 KB |
Program timed out |
2 |
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 |
- |