最长子串回文串 Acwing 139

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;

typedef unsigned long long ull;
const int N = 1e6+10,pk=131;
int h1[N],h2[N],p[N];
char s[N];

ull find(int a,int b,int h[])
{
    return h[b]-h[a-1]*p[b-a+1];
}

int main()
{
    int flag=1;
    while(cin>>(s+1))
    {
        if(s[1]=='E') break;
        p[0]=1;

        int n=strlen(s+1);

        for(int i=1;i<=n;i++)
        {
            h1[i]=h1[i-1]*pk+s[i];
            p[i]=p[i-1]*pk;
        }

        reverse(s+1,s+n+1);

        for(int i=1;i<=n;i++)
        {
            h2[i]=h2[i-1]*pk+s[i];
        }

        int ans=1;
        for(int i=1;i<=n;i++)
        {
            int l=0,r=min(i-1,n-i);
            while(l<r)  //这个二分已经晕了（先奇数区间再偶数区间）
            {
                int mid=(l+r+1)>>1;
                if(find(i-mid,i-1,h1) == find(n-(i+mid)+1,n-(i+1)+1,h2)) l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2+1);

            l=0,r=min(i-1,n-i+1);
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(find(i-mid,i-1,h1) == find(n-(i+mid-1)+1,n-i+1,h2)) l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2);
        }
        cout<<"Case "<<flag<<": "<<ans<<endl;
        flag++;
    }
    return 0;
}