求最长回文子串的长度

本文介绍两种做法，一、manacher算法；二、hash算法加二分(学自《算法竞赛进阶指南》-李煜东著)。

一、我不会啊。。没学，记了个板子：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=110005;
char s[maxn*2],str[maxn*2];
int Len[maxn*2],len;
void getstr(){
    int k=0;
    str[k++]='@';
    for(int i=0;i<len;i++)
        str[k++]='#',
        str[k++]=s[i];
    str[k++]='#';
    len=k;
    str[k]=0;
}
void manacher()
{
    int mx=0,id;
    for(int i=1;i<len;i++)
    {
        if(mx>i) Len[i]=min(Len[2*id-i],mx-i);
        else Len[i]=1;
        while(str[i+Len[i]]==str[i-Len[i]])
            Len[i]++;
        if(Len[i]+i>mx)
            mx=Len[i]+i,id=i;
    }
}
int main()
{
    while(scanf("%s",s)!=EOF){
        len=strlen(s);
         getstr();
        manacher();
        int ans=1;
        for(int i=1;i<len;i++) ans=max(ans,Len[i]);
        printf("%d\n",ans-1);
    }
    return 0;
}

二、hash加二分，本文主要介绍：

分为两部分：

对于字符串，正着和倒着求两个hash数组
枚举回文串的中心位置(1<=i<=n)，分别考虑以i为中心的奇回文串，与偶回文串，设奇回文串的长度为2*p+1，偶为2*q，那么最终结果就是max(2*p+1,2*q)。

1.求hash值：

由于我们求的是hash值的前缀和，那么输入字符串从下标1开始输入较好一点。

hash值数组以及p数组(次幂数组)采用无符号长长整型，这样自然溢出时自动取模，避免了多次取模的低效。

然后正着，倒着各求一个hash数组就好，那么之后我们求一个子串的hash值就是O(1)的操作了：

        int n=strlen(s+1);
        p[0]=1;//
        hash1[0]=0;
        //v为自定义的hash值,p数组为次幂数组;
        for(int i=1;i<=n;++i){
            hash1[i]=hash1[i-1]*v+s[i]-'a'+1;
            p[i]=p[i-1]*v;
        }
        hash2[n+1]=0;
        for(int i=n;i>=1;--i)
            hash2[i]=hash2[i+1]*v+s[i]-'a'+1;

2. 枚举每个位置求奇回文串与偶回文串的最大值：

假设当前枚举中心位置为i，那么我们分别求奇回文串与偶回文串的最大值。

奇回文串的图示：

求最长回文子串的长度

偶回文串的图示：

求最长回文子串的长度

通过观察我们可以发现对于p，q的长度具有二分的性质，即若某一段序列满足回文串性质，那么比他长度小的(中心位置不变)序列也一定满足，故此时只需要确定每一次二分的上界与下界即可解决此题：

首先奇回文串：下界为0，上界为i到串左端点与右端点的距离的较小值(可以手动画一画)；

其次偶回文串：下界为0，上界为 i到左端点的距离+1与(i+1)到右端点的距离+1的较小值。

        int pp=0,q=0;//odd,even;
        int l,r,mid;
        ull x,y;
        for(int i=1;i<=n;++i){//枚举回文串中心;
            l=0,r=min(i-1,n-i);//odd;
            while(l<=r){
                mid=(l+r)>>1;
                x=hash1[i]-hash1[i-mid-1]*p[mid+1];
                y=hash2[i]-hash2[i+mid+1]*p[mid+1];
                if(x==y) l=mid+1;
                else r=mid-1;
            }
            pp=max(pp,r);

            l=0,r=min(i,n-i);//even;
            while(l<=r){
                mid=(l+r)>>1;
                x=hash1[i]-hash1[i-mid]*p[mid];
                y=hash2[i+1]-hash2[i+mid+1]*p[mid];
                if(x==y) l=mid+1;
                else r=mid-1;
                
            }
            q=max(q,r);
            
            
            
        }

时间复杂度：O(n*logn)。

该算法较manacher算法而言，时间开销还是比较大的，而且码量也多一点，属于吃力不讨好型吧23333，就当是一个二分和hash的思考应用吧。

放一道板子题：HDU - 3068

求最长回文子串的长度

相关推荐