最长回文子串--Manacher算法

发表于 2017-10-23

概述

对于求最长回文子串的暴力算法，一般是枚举对称轴然后不断扩展，时间复杂度\(O(n^2)\)。暴力算法有两点缺点： 1. 对称轴可能是一个字母也可能是两个字母之间，需要两次枚举。 2. 扩展可能会出现多余的重复。

而Manacher算法在暴力算法的基础上，做了一些优化，使得复杂度缩小为了\(O(n)\)。 ### Step 1 对于缺点1，可以在字符串中加上一些不会出现的字符作分隔符，这样就可以把“以两个字符的分界线作为对称轴”变为“以两个字符之前的字符作为对称轴”。

比如下面这个字符串： > abcbcbba

可以变为 > #a#b#c#b#c#b#b#a#

可以在最前面和最后面加上另外两个同样不会出现的不同的字符，方便判断边界。（后面全部用新串） ### Step 2 设\(r[x]\)表示以x为中心回文子串的能扩展的最大距离例如 >a#b#c#b#c#b#b#a

以第7个字符(b)为中心能扩展的最大距离是5（第2个字符到第12个字符），所以\(r[7]=5\)

Manacher算法需要用到mx和md两个值,其中mx表示访问的回文子串所能达到的最右端的位置（也就是\(x+r[x]\)的最大值），而md表示扩展到最右端对应的x。比如 >a#b#c#b#c(#)b#b#a

在计算到带括号的#这一位时，mx=12，md=7

算法流程：计算r[x]：当\(x\le mx\)时,r[x]初始化为min(r[x关于md的对称点],mx-x)，否则r[x]初始化为0；

意思是：如果x在这个回文子串中，那么r[x]至少也是和r[x的对称点]和x离最右边界的距离的最小值。

如果r[x的对称点]<=mx-x，那么说明以r的对称点为中心的最长回文子串包含在了以md为中心的最长回文子串中，那么以r为中心的最长回文子串也是这么长。

如果r[x的对称点]>mx-x，那么我们只能确定mx-x这一部分。

接着暴力扩展就好了。暴力扩展就好了。暴力扩展就好了。

然后更新一下mx和md。

复杂度\(O(n)\)，特别神奇。

代码:

/*
Author: CNYALI_LK
LANG: C++
PROG: 1088.cpp
*/
#include<bits/stdc++.h>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define all(x) x.begin(),x.end()
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
template<class T>int chkmin(T &a,T b){return a>b?a=b,1:0;}
template<class T>int chkmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>T sqr(T a){return a*a;}
template<class T>T mmin(T a,T b){return a<b?a:b;}
template<class T>T mmax(T a,T b){return a>b?a:b;}
template<class T>T aabs(T a){return a<0?-a:a;}
#define min mmin
#define max mmax
#define abs aabs
char s[102424];
int a[204848],p[204848];
int js(int x,int l){
    if(x&1)
        if(l&1)
            return (l+1);
        else 
            return l;
    else return l|1;
}
void manacher(int n){
    int mx=0,m=0,ans=0;
    for(int i=1;i<=n;++i){
        if(i>=mx)p[i]=1;
        else p[i]=min(p[m*2-i],mx-i+1);
        while(a[i-p[i]]==a[i+p[i]])++p[i];
        --p[i];
        if(chkmax(mx,i+p[i]))m=i;
//      printf("%d %d\n",p[i]);
        chkmax(ans,js(i,p[i]));
    }   
    printf("%d\n",ans);
}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%s",s+1);    
    a[0]=-1;
    int len=strlen(s+1);
    for(int i=1;i<=len;++i){
        a[i<<1]=s[i];
    }
    int n=2*len+1;
    a[n+1]=-2;
    manacher(n);
    return 0;
}