题目链接：http://poj.org/problem?id=3974
题目大意：
多样例：
每个样例输出它的最长回文串。
T<=30, n<=1000000

思路：想用用字符串水一水，以为会T，结果AC了。时间复杂度：O(T* n * log n)

直接枚举回文中心：二分回文长度。作为奇数回文？还是偶数回文？

用了两个哈希，一个倒着维护。方便判断是否相等。

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
int maxn=1000005;
ull base =131;
char s[1000005];
ull g[2][1000005];
ull p[1000005];
void Hash(char s[])
{
    int len=strlen(s);
    ull ans=0;

    g[0][0]=s[0];
    for(int i=1;i<len;i++)
    {
        g[0][i]=g[0][i-1]*base+s[i];
    }

    g[1][0]=s[len-1];
    int cut=1;
    for(int i=len-2;i>=0;i--, cut++)
    {
        g[1][cut]=g[1][cut-1]*base+s[i];
    }
    return;
}

void getp()
{
    p[0]=1;
    for(int i=1;i<=maxn;i++)
    {
        p[i]=p[i-1]*base;
    }
    return;
}

ull getLR(int l, int r, int k)//取出T里l - r里面的字符串的hash值
{
    if(l==0)
    {
        return g[k][r];
    }
    return g[k][r]-g[k][l-1]*p[r-l+1];
}

int dfs(int i, int mid, int Len, int k)
{
    if(k==0)
    return getLR(i-mid, i-1, 0)==getLR(Len-i-mid-1, Len-i-2, 1);
    if(k==1)
    return getLR(i-mid+1, i, 0)==getLR(Len-i-mid-1, Len-i-2, 1);
}

int main()
{
    int T=1;
    getp();
    while(~scanf("%s",s),s[0]!='E')
    {
        Hash(s);
        int Len=strlen(s), MAX1=0, ID1=0, MAX2=0, ID2=0;
        for(int i=1;i<=Len-2;i++)
        {
            int L=1, R=min(i, Len-i-1), k=0;//奇数
            while(L<=R)
            {
                int mid=(L+R)/2;
                if(dfs(i, mid, Len, 0))
                {
                    L=mid+1;k=mid;
                }
                else
                {
                    R=mid-1;
                }
            }
            if(k>MAX1)
            {
                MAX1=k, ID1=i;
            }

            L=1, R=min(Len-i-1, i+1), k=0;          //偶数
            while(L<=R)
            {
                int mid=(L+R)/2;
                if(dfs(i, mid, Len, 1))
                {
                    L=mid+1;k=mid;
                }
                else
                {
                    R=mid-1;
                }
            }
            if(k>MAX2)
            {
                MAX2=k, ID2=i;
            }
        }
        printf("Case %d: %d\n",T++,max(MAX2*2, MAX1*2+1));
        
/***********************输出回文串*******************************/
// if(MAX2*2>MAX1*2+1)
// {
// for(int i=ID2-MAX2+1;i<=ID2+MAX2;i++)
// {
// printf("%c",s[i]);
// }
// }
// else
// {
// for(int i=ID1-MAX1;i<=ID1+MAX1;i++)
// {
// printf("%c",s[i]);
// }
// }
// printf("\n");
    }

    return 0;
}