题目链接
1 #include <bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 inline ll read(){
5 int x=0,f=1;char ch=getchar();
6 while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
7 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
8 return x*f;
9 }
10
11 /***********************************************************/
12
13 const int maxn = 11000000;
14 char s[maxn], now[maxn*2+5];
15 int te, p[maxn*2+5];
16
17 int manacher(char *s){
18 int len = strlen(s+1);
19 for(int i = 1;i <= len;i++){
20 now[2*i-1] = '#';
21 now[2*i] = s[i];
22 }
23 len = len*2+1;
24 now[len] = '#';
25 int pos = 0, r = 0;
26 for(int i = 1;i <= len;i++){
27 if(i < r) p[i] = min(p[2*pos-i], r-i);
28 else p[i] = 1;
29 while(1 <= i-p[i] && i+p[i] <= len && now[i-p[i]] == now[i+p[i]]) p[i]++;
30 if(i+p[i] > r) {
31 pos = i;
32 r = i+p[i];
33 }
34 }
35 int Max = 0;
36 for(int i = 1;i <= len;i++)
37 Max = max(Max, p[i] - 1);
38 return Max;
39 }
40
41 int main(){
42 while(~scanf("%s", s+1)){
43 int ans = manacher(s);
44 printf("%d
", ans);
45 }
46 return 0;
47 }