题目描述:略

解法1：hash

预处理前后hash的值,再一个一个枚举
按奇数和偶数判断情况,二分判断

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int P=13331;
const int N=1e6+1e3;
char s[N];
int f1[N],f2[N],p[N];
int ans,n;
int H1(int x,int y){return f1[y]-f1[x-1]*p[y-x+1];}
int H2(int x,int y){return f2[x]-f2[y+1]*p[y-x+1];}
signed main()
{
    p[0]=1;
    for(int i=1;i<=N-100;i++)p[i]=p[i-1]*P;
    int _=0;
    while(++_)
    {
        ans=0;
        scanf("%s",s+1);if(s[1]=='E')return 0;
        n=strlen(s+1);f1[0]=0;f2[n+1]=0;
        for(int i=1;i<=n;i++)
            f1[i]=f1[i-1]*P+s[i];
        for(int i=n;i;i--)
            f2[i]=f2[i+1]*P+s[i];
        for(int i=1;i<=n;i++)
        {
            //枚举奇数中点
            int l=0,r=min(i-1,n-i);//因为i为中点
            //二分枚举一半的长度(l),所以l可能0
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(H1(i-mid,i-1)==H2(i+1,i+mid))l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2+1);
            //枚举偶数
            l=0,r=min(i-1,n-i+1);//枚举为偶数串的
            //i被算到右边了
            while(l<r)
            {
                int mid=l+r+1>>1;
                if(H1(i-mid,i-1)==H2(i,i+mid-1))l=mid;
                else r=mid-1;
            }
            ans=max(ans,l*2);
        }
        printf("Case %d: %d\n",_,ans);
    }
}

解法2:Manacher,不过适用性很小。

洛谷模板
感觉verygood的讲解
manacher,有点类似kmp的感觉。
首先用一个神奇的方法,把每个数之间之间插上一个’#’,首位再额外插上两个’#’,再首位再插上两个不同的符号(‘!’和’?’).

这样有什么好处呢?

rt,首先偶数和奇数都变成奇数了

abc -> !#a#b#c#?

abac -> !#a#b#a#c#?

如果以b为中点,他扩展的长度是奇数。

如果以#为中点,他们扩展的长度一定小于以字母为中点的。所以他们对答案没有影响.

为什么会这样呢? n+n-1+2+2=2n+3 -> 2n是偶数,3是奇数,偶+奇=奇。

还有一个神奇的性质

若以字符为中点,他扩展的长度(回文半径)(一边)-1等于他的回文串长度.but,why?

(回文半径,有一个回文串,长度为n,若n为奇数,回文半径为(n-1)/2+1,若n为偶数,回文半径为n/2)

假如有一个回文串,长为n

当加上’#’时,仍然是回文串,长度为n+n-1+2=2n+1(+2是因为我们把这个回文串外面也加上了’#’).因为是奇数,所以回文半径为(2n+1-1)/2+1=n+1.n+1-1=n,命题得证。

这也说明了为什么还要在整个字符串外面再加上两个’#’,是为了凑出上面这个式子。至于’!’和’?’,判边界用的,是为了枚举到边界时自动停止。

我们再来思考怎么算出他扩展的半径。

于是这个算法又给出了一个很神奇的解法。我们设p[i]表示以i为中心,最长回文串的半径。

假设现在有一个回文串。

!#a#b#c#b#b#c#?

我们假设他已经枚举到了i。前面p[1~i-1]都已经得到。

我们现在知道一个事情:若在同一个大回文串的两个小回文串,与大回文串的中心成对称,那么他们两个必定全等(因为对称,可以理解为翻过来)。

所以我们可以以一个回文串的中心mid为i的对称点,我们设另一个i关于mid的对称点为j,可以根据中点公式求得:(i+j)/2=mid -> j=mid*2-i. 所以p[i]=p[j].

但上式不是完全正确。还需考虑几个特殊情况:

1.j落在这个大回文串的最左边,这时i落在这个大回文串的最右边,若p[j]>1,但这时以j为中心的小回文串不一定与i的对称,同理,j-p[j]+1<大回文串的最左边 亦或其他情况也是如此,这时我们记录i在这个大回文串的最长长度不能超过大回文串的边界,这时我们就需要暴力拓展。

2.i出到大回文串外面了,这时也要枚举。

但我们还有一个问题,这个大回文串该怎么更新?,我们的答案是,为右端点的位置大于前面的所有为标准进行更新。但我们机房已经有大佬口胡出来，这里我就把他的思路抄一遍。

我们设原先回文串左端点和右端点为l1和r1。

设按上面的条件进行更新的回文串左端点和右端点为l2和r2。

则r2>r1.

我们分以下几种情况进行考虑。

1.l1<l2,则两个回文串互不影响,第一个回文串的价值已经利用尽了,所以要换到第二个.

2.l1>=l2,则两个回文串相交,我们再分情况考虑

我们假设有一个字符的下标为i

p1:i不在相交处,这样第一个回文串枚举不到,选择第二个回文串

p2:i在相交处,若i在第二个回文串中心的左边,没有意义,因为已经算过了,我们只考虑相交处在第二个回文串对称中心的右边的i.但因为即使i以第一个字符串中心进行更新,长度依然在第一个回文串的r1内,不会超过第二个回文串的右边界,而以第二个回文串为中心对称的长度的,肯定大于等于第一个回文串中心对称所返回的长度(因为在第一个回文串长度内,三个东西互相相等,而在第二个回文串长度外,以第一个回文串中心对称的长度没有扩展到,所以不知道,而处在以第二个回文串为中心对称长度,处在第二个回文串的范围内,更新过,所以更优)

所以我们选择更右边的。

#include<bits/stdc++.h>
using namespace std;
const int N=1001000;
char s1[N],s[N];
int p[N];
int n,m;
int main()
{
    int _=0;
    while(++_)
    {
        scanf("%s",s1+1);
        if(s1[1]=='E')return 0;
        m=strlen(s1+1);
        n=0;
        s[0]='?';s[++n]='#';
        for(int i=1;i<=m;i++)
            s[++n]=s1[i],s[++n]='#';
        s[++n]='!';
        int mid=1,mx=1,ans=-1;
        //mid,当前回文串中心,mx,右端点,ans,答案
       // for(int i=0;i<=n;i++)cout<<s[i];puts("");
        for(int i=1;i<n;i++)
        {
            if(i<mx)p[i]=min(mx-i,p[mid*2-i]);
            //如果没到右端点   防止出边界
            else p[i]=1;
            //重新计算
            while(s[i-p[i]]==s[i+p[i]])p[i]++;
            //枚举
            if(mx<i+p[i])mid=i,mx=i+p[i];
            //更新回文串中心
            ans=max(ans,p[i]-1);
        }
        printf("Case %d: %d\n",_,ans);
     //  return 0;
    }
}