之前用字符串hash+二分过了，今天刚看了manacher拿来试一试。
这manacher也快太多了%%%
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 1e6 + 5; 8 char s[maxn], tmp[2*maxn]; 9 int p[maxn*2], id, mx, ans; 10 inline void manacher(){ 11 mx = id = ans = 0; 12 memset( p, 0, sizeof(p) ); 13 for( int i=1; tmp[i]; i++ ){ 14 p[i] = mx>i ? min(p[2*id-i], mx-i):1; //因为i >= id 所以找其在左侧已经求出的对称点2*id-1 15 while( tmp[i+p[i]]==tmp[i-p[i]] ) p[i]++; 16 if( mx<i+p[i] ){ 17 mx = i+p[i]; 18 id = i; 19 } 20 } 21 for( int i=1; tmp[i]; i++ ) 22 if( ans<p[i] ) ans = p[i]; 23 } 24 25 int main(){ 26 int kase = 0; 27 while( ~scanf("%s", s+1) && s[1]!='E' ){ 28 int len = strlen(s+1); 29 tmp[0] = '$'; 30 int j = 2; 31 for( int i=1; i<=len; i++, j+=2 ){ 32 tmp[j+1] = tmp[j-1] = '#'; 33 tmp[j] = s[i]; 34 } 35 tmp[j+2] = 0; 36 manacher(); 37 printf("Case %d: %d ", ++kase, ans-1); 38 } 39 40 return 0; 41 } 42 /* 43 Sample Input 44 45 abcbabcbabcba 46 abacacbaaaab 47 END 48 Sample Output 49 50 Case 1: 13 51 Case 2: 6 52 */