Manacher

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 3e5;
 4 char s[maxn], str[maxn];
 5 int len1, len2, p[maxn], ans;
 6 
 7 void init(){
 8     str[0] = '$';
 9     str[1] = '#';
10     for(int i=0; i<len1; i++){
11         str[i*2+2] = s[i];
12         str[i*2+3] = '#';
13     }
14     len2 = len1 << 1 + 2;
15     str[len2] = '*';
16 }
17 void manacher(){
18     int id=0, mx=0;
19     for(int i=1; i<len2; i++){
20         if(mx>i)p[i]=min(p[id<<1-i], mx-i);
21         else p[i]=1;
22         for(;str[i+p[i]] == str[i-p[i]];p[i]++);
23         if(p[i]+i > mx){
24             mx=p[i]+i;
25             id = i;
26         }
27     }
28 }
29 int main(){
30     //freopen("in", "r", stdin);
31     while(scanf("%s", s), strcmp(s,"end")){
32         len1 = strlen(s);
33         init();
34         manacher();
35         for(int i=0; i<len2; i++)
36             ans = max(ans, p[i]);
37         printf("%d
", ans);
38     }
39 }