题目大意：输入字符串，求出其中最长回文串的长度，输入”END”结束测试
1.从下标一开始输入字符串
2.回文串分为奇数回文串和偶数回文串，在字符串的每个字母前添加一个
大于’z’的字符，使得可能存在的回文串变成奇数回文串
3.计算出正反哈希
4.枚举出所有可能的回文串中点
5.二分求出在某个确定中点下的奇数回文串的半径长度,l,r分别为半径的
左极限和右极限,mid为半径
6.枚举的过程中可能存在两种情况，
1)不是回文串 -> 缩小范围
2)是回文串 -> 扩大范围
5.奇数回文串也可能存在两种范围
1)以非字母字符为边界，即非字母比字母多一个则(2 * l - 1) / 2向下取
整，长度为l
2)以字母为边界， 向上取整l+1

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef unsigned long long ULL;
const int N = 2000010,P = 131;

char str[N];
ULL hl[N],hr[N],p[N];

ULL get(ULL h[],int l,int r)
{
    return h[r] - h[l-1] * p[r-l+1];
}

int main()
{
    int T = 1;
    while(scanf("%s",str+1),strcmp(str+1,"END"))//逗号表达式的返回值是最后一个表达式的值 
    {
        int n = strlen(str+1);

        for(int i = 2 * n; i >= 1; i -= 2)//要确保i为偶数，因此表达式3的值为i -= 2 
        {
            str[i] = str[i/2];
            str[i-1] = 'z' + 1;//在每个字母前插入一个非字母字符，这样就只用考虑回文串长度为奇数的情况了 
        }

        n *= 2;//数组的有效长度需要扩大二倍

        p[0] = 1;
        for(int i = 1,j = n; i <= n; i++,j--)
        {
            hl[i] = hl[i-1] * P + str[i];//正哈希
            hr[i] = hr[i-1] * P + str[j];//反哈希 
            p[i] = p[i - 1] * P;
        } 
        int res = 0; 
        for(int i = 1; i <= n; i++)// 枚举回文串中点，二分求半径 
        {
            /*
            二分回文串半径，如果当前半径的串不是回文，说明回文串半径更小
            否则说明回文串的长度可能更大 
            */
            int l = 0,r = min(i-1,n-i);//二分的最小半径为 l = 0最大半径为 r 
            //###l和r为某确定中点时的半径的左右极限 
            while(l < r)
            {
                int mid = l + r + 1 >> 1;//mid为半径，因为 l = mid 所以需要写为 l + r + 1 防止出现死循环 
                if(get(hl,i - mid,i - 1) != get(hr,n - (i + mid) + 1,n - (i + 1) + 1)) r = mid - 1;// ### 如果不是回文说明太长了，即 mid 太大了需要缩小半径的范围 
                //i + 1 和 i + mid是正序（从左向有数）的下标，但现在需要求的是逆序（从右向左数）的下标 
                else l = mid;
                //否则需要增大半径的范围 
            }
            //结束循环时 l = r，res为包含特殊符号的回文串长度，但要求的是不包含#的回文串 
            //半径是l
            if(str[i - l] <= 'z') res = max(res,l+1); //如果回文串的最外层是字母,字母比#多一个 
            else res = max(res,l);//如果回文串的最外层是#，则#比字母多一个 
            //因为有多个res所以必须用擂台法进行更替 
        }
        printf("Case %d: %d\n",T++,res);
    }   
    return 0;
}