算法1

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string.h>
#include<string>
#include<cstdio>
#include<vector>
#include<deque>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef unsigned long long ULL;
const int maxn = 2e6 + 5,base = 131;  // 范围应开到 2 ~ 3 倍,防止出现段错误 
ULL HashL[maxn],HashR[maxn],p[maxn];
char str[maxn];
int res = 0,len;
int main(void) {
    void init();
    void solve();
    int t = 1;
    while(scanf("%s",str + 1),strcmp(str + 1, "END") ) {
        init();
        res = 0;
        solve();
        printf("Case %d: %d\n",t ++,res);
    }
    return 0;
}
void init() {
    len = strlen(str + 1);
    len *= 2;                                              // 因为你要往两个字符中间插一个字符(所以需要扩大数组的空间) 
    for(int j = len; j > 0; j -= 2) {
        str[j] = str[j / 2];
        str[j - 1] = 'a' + 26;
    }
    HashL[0] = 0,HashR[len] = 0,p[0] = 1;
    for(int i = 1,j = len; i <= len; i ++,j --) {
        HashL[i] = HashL[i - 1] * base + str[i] - 'a' + 1;
        HashR[i] = HashR[i - 1] * base + str[j] - 'a' + 1; // 只要每次加的字符不一样，所得到的哈希值就会有所不同,所以可以直接进行操作 
        p[i] = p[i - 1] * base;
    }
    return ;
}
ULL get1(int L,int R) {
    return HashL[R] - HashL[L - 1] * p[R - L + 1];
}
ULL get2(int L,int R) {
    return HashR[R] - HashR[L - 1] * p[R - L + 1];
}
void solve() {
    for(int i = 1; i <= len; i ++) {
        int L = 0,R = min(i - 1,len - i);                 // 回文串的半径长度 
        while(L < R) {
            int mid = (L + R + 1) >> 1;
            /* get2(i + 1,i + mid) 是正序，而我们应该得到的是反序，所以需要对其进行操作 
               正序 ： 1    反序 : n
                       2           n - 1
                       3           n - 2
                       x           n - x + 1
            */ 
            if(get1(i - mid,i - 1) != get2(len - (i + mid) + 1,len - (i + 1) + 1)) {
                R = mid - 1;
            } else {
                L = mid;
            }
        }
        if(str[i - L] <= 'z') res = max(res,L + 1);   // 求回文串的实际长度 
        else res = max(res,L);
    }
    return ;
}