题目描述
如果一个字符串正着读和倒着读是一样的，则称它是回文的。
给定一个长度为N的字符串S，求他的最长回文子串的长度是多少

输入
输入将包含最多30个测试用例，每个测试用例占一行，以最多1000000个小写字符的形式给出。

输入以一个以字符串“END”（不包括引号）开头的行表示输入终止。

直接中文翻译，就是爽。

分析
普通思路，字符串hash+二分答案。
先观察一下回文串的性质，一般的，可以分为奇数串和偶数串，奇回文串A，顾名思义，长度为奇数M，所以它的中心点是一个字符，并且图片说明
偶回文串A，就是长度为偶数M，它的中心点就是两个字符之间的夹缝，并且图片说明
所以在本题中，我们可以枚举回文子串的中心位置，看这个中心位置能向两边延伸多长。
直接搬代码

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned long long

int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f; 
}
const int N=1e6+10,P=13331;

char s[N];
uint f1[N];//顺着 
uint f2[N];//倒着 
uint p[N];//次方 

uint H1(int x,int y)//正着 
{
    return (f1[y]-f1[x-1]*p[y-x+1]);
}
uint H2(int x,int y)//倒着 
{
    return (f2[x]-f2[y+1]*p[y-x+1]);
}

signed main()
{
    int cnt=0;
    p[0]=1;
    for(int i=1;i<N;i++)
        p[i]=p[i-1]*P;
    while(scanf("%s",s+1)&&!(s[1]=='E'&&s[2]=='N'&&s[3]=='D'))
    {
        ++cnt;
        int len=strlen(s+1);
        int ans=0;
        f2[len+1]=0;
        for(int i=1;i<=len;i++)
            f1[i]=f1[i-1]*P+s[i];
        for(int i=len; i;i--)
            f2[i]=f2[i+1]*P+s[i];
        for(int i=1;i<=len;i++)
        {
            int l=0;//二分答案 
            int r=min(i-1,len-i);

            //cout<<"偶"<<l<<" "<<r<<endl; 

            while(l<r)
            {
                int mid=(l+r+1)>>1;//此mid就是书上的p 
                if(H1(i-mid,i-1)==H2(i+1,i+mid))//偶回文子串 
                    l=mid;
                else r=mid-1;
            }
            ans=max(l*2+1,ans);
            l=0,r=min(i-1,len-i+1);

            //cout<<"奇"<<l<<" "<<r<<endl;

            while(l<r)
            {
                int mid=(l+r+1)>>1;//此mid就是书上的q 
                if(H1(i-mid,i-1)==H2(i,i+mid-1))//奇回文子串 
                    l=mid;
                else
                    r=mid-1;
            }
            ans=max(l*2,ans);
        }
        printf("Case %d: %d\n",cnt,ans);    
    }
    return 0;
}

你以为这就完了，不可能，我们还可以优化那么一下下，你看啊，如果就找上面的做法，我们需要分别处理奇回文串和偶回文串的问题，要进行两次二分答案，这样就很烦，因为二分本来就不好写，一不留神就写错了，还不容易发现，那有什么办法呢。

我们可以考虑在每一个字符后面都加一个#（其实啥都可以，只要不影响判断原本的字符就行了），加了字符后，我们就会惊奇地发现，每一个字符串都变成奇数了（其实就是简单的奇加偶得奇的事），那这样我们不就好办了，同样直接上代码

#include<bits/stdc++.h>
using namespace std;
#define uint unsigned long long

int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
    return x*f; 
}
const int N=2e6+10,P=131;
char s[N];
uint f1[N];
uint f2[N];
uint p[N];

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

signed main()
{
    int T=1;
    while(scanf("%s",s+1)&&strcmp(s+1,"END"))
    {
        int len=strlen(s+1);
        for(int i=len*2;i;i-=2)
        {
            s[i]=s[i/2];
            s[i-1]='z'+1;
        }
        len*=2;
        p[0]=1;
        for(int i=1,j=len;i<=len;i++,j--)
        {
            p[i]=p[i-1]*P;
            f1[i]=f1[i-1]*P+s[i]-'a'+1;
            f2[i]=f2[i-1]*P+s[j]-'a'+1;
        }
        int ans=0;
        for(int i=1;i<=len;i++)
        {
            int l=0;
            int r=min(i-1,len-i);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(H(f1,i-mid,i-1)!=H(f2,len-(i+mid)+1,len-(i+1)+1))
                    r=mid-1;
                else
                    l=mid;
            }
            if(s[i-l]<='z')
                ans=max(ans,l+1);
            else
                ans=max(ans,l);
        }
        printf("Case %d: %d\n",T++,ans);
    }
    return 0;
}

我发现这是这题唯一的题解，赶紧抓紧机会，都看到这了，不点个赞？