#include<stdio.h>
#include<algorithm>
const int L_ = 300030;
const int LL = 20;
char ch[L_], ch2[L_+L_];
int ord[L_+L_], sa[L_];
int tmp[LL][L_], T, n;
int D[L_+L_];
int LCP[L_][LL];
long long ans;
bool comp(const int &a, const int &b){return ord[a] != ord[b] ? ord[a] < ord[b] : ord[a+T] < ord[b+T];}
int main(){
scanf("%s",ch);
int i, now = 0;
for(i=0;ch[i];i++)sa[i] = i, ord[i] = ch[i];
n = i;
while(T<n){
std::sort(sa,sa+n,comp);
int cnt = 0;
for(i=0;i<n;i++){
if(i!=0 && (ord[sa[i]] != ord[sa[i-1]] || ord[sa[i]+T] != ord[sa[i-1]+T]))cnt++;
tmp[now][sa[i]] = cnt;
}
for(i=0;i<n;i++)ord[i] = tmp[now][i];
T = T?2*T:1;
now++;
}
for(i=0;i<n;i++)sa[ord[i]] = i;
for(i=1;i<n;i++){
int x = sa[i], y = sa[i-1];
for(int j=now-1;j>=0;j--)if(tmp[j][x] == tmp[j][y]){
x += 1<<j, y += 1<<j, LCP[i][0] += 1<<j;
}
for(int j=1;j<LL;j++){
if(i < (1<<j))break;
LCP[i][j] = std::min(LCP[i][j-1], LCP[i-(1<<j)][j-1]);
}
}
for(i=0;i<n;i++){
ch2[i+i] = ch[i];
ch2[i+i+1] = '-';
}
int m = 2*n-1, c = -1, r;
for(i=0;i<m;i++){
if(c >= i && D[r+r-i] < c-i)D[i] = D[r+r-i];
else{
r = i;
while(c+1 < m && c < i+i && ch2[c+1] == ch2[i+i-c-1]){
if(!(++c & 1)){
int S = (i+i-c)/2, len = c-i+1;
int right = ord[S], left = ord[S];
for(int j=LL-1;j>=0;j--)if(right+(1<<j) < n && LCP[right+(1<<j)][j] >= len)right += 1<<j;
for(int j=LL-1;j>=0;j--)if(left >= (1<<j) && LCP[left][j] >= len)left -= 1<<j;
ans = std::max(ans, (long long)(right - left + 1) * len);
}
}
D[i] = c - i;
}
}
printf("%lld",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
54704 KB |
Output is correct - answer is '7' |
| 2 |
Incorrect |
0 ms |
54704 KB |
Output isn't correct - expected '4', found '6' |
| 3 |
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 |
- |
