1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char s[11000110],s2[33000300];
int p[33000300];
int init(){
int len=strlen(s);
s2[0]='%';
s2[1]='#';
int j=2;
for(int i=0;i<len;i++){
s2[j++]=s[i];
s2[j++]='#';
}
s2[j]='*';
return j;
}
int manacher(){
int len=init();
int maxLen=-1;
int id,mx=0;
for(int i=1;i<len;i++){
if(i<mx) p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(s2[i-p[i]]==s2[i+p[i]]) p[i]++;
if(mx<i+p[i]) id=i,mx=i+p[i];
maxLen=max(maxLen,p[i]-1);
}
return maxLen;
}
int main(){
gets(s);
printf("%d",manacher());
return 0;
}
|