题目描述

如果一个字符串正着读和倒着读是一样的，则称它是回文的。

给定一个长度为$N$的字符串$S$，求他的最长回文子串的长度是多少。

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

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

输出格式
对于输入中的每个测试用例，输出测试用例编号和最大回文子串的长度（参考样例格式）。

每个输出占一行。

样例

输入样例：
abcbabcbabcba
abacacbaaaab
END
输出样例：
Case 1: 13
Case 2: 6

前缀和+后缀和+二分+Hash(哈希) $O(nlogn)$

我们发现0这道题目数据范围极其恐怖,那么只有一个办法可以让我们求解这道题目,那就是哈希,或者是$O(n)$复杂度的Manacher算法,但是我们这道题目是锻炼我们的哈希水平,所以我们这里只说如何用哈希算法求解.作者忘记如何使用马拉车算法了…

上一道兔子兔子兔子的题目,我们知道判断两个字符串是否相等,可以使用字符串哈希,也就是将字符串算成P进制数值,然后区间和判断即可,那么这道题目我们需要一个正的字符串,还需要一个反的字符串,然后如果正字符串等于反的字符串,那么奇数回文串就2+1,偶数回文串就直接2即可.之所以要这么做,因为我们是要回文对不对,我们需要将回文拆解成为一个正字符串和一个反字符串,这样才好处理这道题目.

既然如此,我们可以算出一个前缀和,再算出一个后缀和,然后就可以知道,正字符串和一个反字符串.字符串的哈希值就是这个区间的哈希值和.

算完之后,我们当前就只需要枚举一个mid中间点,因为所有回文串都是有一个中间点(奇),或者中间区间(偶),然后二分分别寻找这个字符串长度即可,记住不是回文串,回文串的长度,是字符串长度* 2 + 1(奇) 或者是字符串长度 * 2(偶数).

切记如果说这个最大回文串为1(也就是所有字符都不一样,比如说abcdefg),那么输出是1,不是3,奇数回文串=奇数字符串*2+1,你们要小心特判这种情况,或者处理二分边界.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define fir(i,a,b) for(int i=a;i<=b;i++)
#define fic(i,a,b) for(int i=a;i>=b;i--)
#define Mod 131 //P进制
const int N=1000007;
char s[N];
ull f1[N],f2[N],p[N];
int ans,t,l,r,mid;
ull Hash1(int i,int j)//正字符串的哈希值
{
    return (f1[j]-f1[i-1]*p[j-i+1]);
}
ull Hash2(int i,int j)//反字符串的哈希值
{
    return (f2[i]-f2[j+1]*p[j-i+1]);
}
void init()
{
    p[0]=1;//p^0为1
    fir(i,1,N-1)
        p[i]=p[i-1]*131;//P进制的位值
}
int main()
{
    init();
    while (++t)
    {
        ans=0;
        scanf("%s",s+1);
        int len=strlen(s+1);
        if (strcmp(s+1,"END")==0) //结束读入
            return 0;
        f2[len+1]=0;//初始化要注意,不然的话容易GG
        fir(i,1,len) 
            f1[i]=f1[i-1]*Mod+(s[i]-'a'+1);//前缀和
        fic(i,len,1)
            f2[i]=f2[i+1]*Mod+(s[i]-'a'+1);//后缀和
        fir(i,1,len)
        {
            l=0,r=min(i-1,len-i);//二分枚举长度为奇数的字符串 记住这里l一定要为0,不然的话,你会发现最后一个数据会卡死你.
            while(l<r)
            {
                mid=l+r+1>>1;
                if (Hash1(i-mid,i-1)==Hash2(i+1,i+mid))//如果这是一个回文串的话
                    l=mid;
                else
                    r=mid-1;
            }
            ans=max(l<<1 | 1,ans);//算出最大长度
            l=0,r=min(i-1,len-i+1);//偶数字符串
            while (l<r)
            {
                mid=l+r+1>>1;
                if (Hash1(i-mid,i-1)==Hash2(i,i+mid-1))//check判断
                    l=mid;
                else
                    r=mid-1;
            }
            ans=max(l<<1,ans);//偶数字符串只需要*2
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}