YBT132 回文子串

传送门：YBT132 回文子串

样例输入

abcbabcbabcba
abacacbaaaab
END

`样例输出`

Case 1: 13 
Case 2: 6

题解

　　该题解面向新手

　　首先我们可以发现一个字符串的hash值和倒过来的hash值相等（也就是倒过来是同一个字符串），那么他是回文的。

　　那么现在问题来了，我们怎么找到最大的回文子串呢？根据题目和数据范围容易发现使用二分答案。

　　也就是说，二分最大长度，O(n)枚举是否存在（通过hash预处理）

　　大概的思路有了，但众所周知回文字符串分为奇串和偶串，也就是说不存长度为5的回文串时，可能还存在长度为6的。

　　比如aaabaaa, 不存在长度为6，4的子串。读者仔细思考发现，答案不单调无法二分。

　　但你想，事实上奇数和偶数长度分别都是单调的：不存在长度为5的子串，就一定不存在长度为7， 9， 11、、、的子串回文，偶数易燃。

　　这就有很多处理方法了，比如manache什么的，不过这里讲一种麻烦但新手容易想到的方法

　　　　奇偶串分别二分

　　有点累，可以看看代码细节....

　　宁还是别看了，多组数据不清空....陆陆续续调了个好几天，实在看不了，抱歉，太累了没法改了

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string.h>
 4 #define ull unsigned long long
 5 using namespace std;
 6 
 7 const int N = 2000005;
 8 const ull b=231, p=233371;
 9 char s[N];
10 int len, T=0;
11 ull hash1[N], hash2[N], c[N];
12 
13 ull getHash1(int l, int r){
14     if(l == 0) return hash1[r];
15     return ((hash1[r] - hash1[l-1]*c[r-l+1]) );
16 }
17 
18 ull getHash2(int l, int r){
19     if(r == N) return hash2[r];
20     return ((hash2[l] - hash2[r+1]*c[r-l+1]) );
21 }
22 
23 int main(){
24     c[0]=1;
25     for(int i=1; i<N; i++) c[i] = (c[i-1]*b); 
26     while(++T){
27         for(int i=0; i<N; i++) s[i]=0, hash1[i] = hash2[i] = 0;
28         cin >> s;
29         if(!strcmp(s, "END")) return 0;
30         
31         len=strlen(s), hash1[0]=s[0], hash2[len-1]=s[len-1];
32         
33         for(int i=1; i<len; i++) hash1[i] = (hash1[i-1]*b + (ull)s[i]);
34         for(int i=len-2; i>=0; i--) hash2[i] = (hash2[i+1]*b + (ull)s[i]);
35         
36         int ans = 1, l=1, r=len;
37         while(l<r){
38             int mid = (l+r)/2, flag=1;
39             if(mid%2) mid++;
40             for(int i=0; i+mid-1<len; i++){
41                 if(getHash1(i, i+mid-1) == getHash2(i, i+mid-1)){
42                     flag=0;
43                     ans = mid;
44                     l = mid + 1;    
45                     break;                
46                 }
47             }
48             
49             if(flag) r = mid - 1;
50         }
51         
52         l=1, r=len;
53         while(l<r){
54             int mid = (l+r)/2, flag=1;
55             if((mid%2)==0) mid++;
56             for(int i=0; i+mid-1<len; i++){
57                 if(getHash1(i, i+mid-1) == getHash2(i, i+mid-1)){
58                     flag=0;
59                     ans = max(mid, ans);
60                     l = mid + 1;    
61                     break;                
62                 }
63             }
64             
65             if(flag) r = mid - 1;
66         }
67         
68         cout << "Case " << T << ": " << ans << endl;
69         
70     } 
71 }