原题链接

考察：字符串hash+二分

这道题和前面的查找子串的题一样用到二分,答案都具有单调性,但这道题的单调性不是上道题那么明显.本道题不是简单地枚举端点,如果枚举端点当然没有单调性,本道题是用中心扩展思想(不是第一次学,但我完全不记得).选取一个端点为中心,扩散到两边看是否为回文串.因为这道题是hash练习题所以用hash做,

中心扩展回文本来要分是偶数串还是奇数串,但我们可以通过一些小技巧全部化为奇数串：   即在字符间插入其他字符  

但是这样在二分判断的时候,返回的长度不一定是答案的长度,比如a#a,这个字符串是回文的,但实际长度只有2.又比如d#a#b#a#c,这个字符串的子字符串也回文,但是实际长度是3.因此当加入新的操作的时候,要考虑此操作对其他操作的影响,这个在uva链表的例题也是有体现的

思路：
       将字符#插入,求正向和逆向的hash,枚举中心点二分答案

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 const int N = 2000010;
 5 const int P = 133;
 6 typedef unsigned long long ull;
 7 ull h[N],p[N],rh[N];
 8 char s[N>>1],a[N];
 9 int len,ans,kcase;
10 int Get(int l,int r,int id)
11 {
12     if(!id) return rh[l]-rh[r+1]*p[r-l+1];
13     return h[r]-h[l-1]*p[r-l+1];
14 }
15 bool check(int mid,int i)
16 {
17     if(Get(i-mid,i-1,1)==Get(i+1,i+mid,0)) return true;
18     return false;
19 }
20 int main()
21 {
22     while(scanf("%s",s+1)!=EOF&&strcmp(s+1,"END")!=0)
23     {
24         fill(p,p+N,0);  fill(h,h+N,0); fill(rh,rh+N,0); fill(a,a+N,0);
25         p[0] = 1; ans = 0;
26         len = strlen(s+1);
27         for(int i=1,j=1;i<=len;i++){
28             a[j++] = s[i]; a[j++] = '#';
29         }
30         a[2*len] = '\0';
31         len = 2*len-1;
32         for(int i=1;i<=len;i++){
33             h[i] = h[i-1]*P+a[i]-'a'+1;
34             p[i] = p[i-1]*P;
35         }
36         for(int i=len;i>0;i--) 
37         {
38             rh[i] = rh[i+1]*P+a[i]-'a'+1;//中心扩展思想
39         }
40         for(int i=1;i<=len;i++){
41         //    printf("检验字符是%c\n",a[i]);
42             int low = 0,high = min(i-1,len-i);//这个min避免了越界问题 
43             while(low<high){
44                 int mid = low+high+1>>1;
45                 if(check(mid,i)) low = mid;
46                 else high = mid-1;
47             }
48             if(a[i-low]!='#') ans = max(ans,low+1);//因为加入了#,所以答案不是简单的low
49             else ans = max(ans,low);
50         }
51         printf("Case %d: %d\n",++kcase,ans);
52     }
53     return 0;
54 }