最近准备总结一下常用的字符串算法,今天就让我们从最经典的回文串算法——Manacher开始吧!

什么是回文串

“回文串”,就字面而言,就是是一个正读和反读都一样的字符串。比如“level”就是一个回文串,但是“love”就不是一个回文串。
1.PNG

那么如何求解回文串呢?朴素的来想,我们只需要枚举原序列中的点k,接着从k点向左右拓展直到拓展到的左端和右端字符不一样;这样操作就可以得到一个O(n^2)的算法。

但是1975年,一个叫Manacher的十分聪明的人发明了一个算法,并命名为Manacher算法(中文名:马拉车算法),运用该算法可以把时间复杂度提升到O(n)。

下面就让我们一起走进神奇的Manacher算法。

Manacher过程详解

首先,由于回文串分为奇数长度的回文串和偶数长度的回文串,为了方便处理,我们在开头结尾以及任意两个字符之间都插入一个“%”,这样我们就只用考虑长度为奇数的回文串就可以了。
2.PNG

接下来就是Manacher的精髓了。我们对于任意一个点i,都定义一个值 p【i】 表示 以 i 为中心的最长回文的半径。

例如对于一个字符串 a b b a h o p h p ;第一次操作后得到序列 % a % b % b % a % h % o % p % h % p % ;接下来我们手算一下p数组——

3.PNG

可以看出,p[i] - 1正好是原字符串中最长回文串的长度。

关键就在于如何快速求解p数组,如果利用暴力求解,不就和暴力一样了吗?

首先,我们需要定义两个全局变量:

pos:表示当前求解到的所有回文串中,右端点最右的回文串的中心在哪里;
r:表示pos所在中心的字符串的右端点究竟在哪里。

如下图,我们把方框当成回文串,则我们很明显的看到,浅黄色的回文串的右端点在最右边,所以以它的中点为pos,右端点为r:

4.PNG

也就是说,我们每求得一个新的回文串,就要尽可能的更新一次pos和r。

接下来让我们回到求p【i】的问题上来,假设我们现在求p[i],也就是以 i 为中心的最长回文半径,那么我们只要对i分成两种情况:

1.i<=r 也就是说,i在 以 pos 为中心的回文串内;

这样的话有什么好处吗?我们观察一下下面这幅图:

5.PNG

我们用黄色方框以j为中心的回文串,此时又分为两种情况:

1.当j的回文串比较短,在以pos为中心的回文串之内:

由于i,j同在一个回文串内,且关于pos对称,所以以i为中心的红色回文串一定有一个和黄色回文串相同;即此时p【i】=p【j】;

6.PNG

2.当j的回文串比较长,超出了以pos为中心的回文串:

此时,以i为中心的回文串的最右只能到r;

7.PNG

为什么不能和以j为中心的回文串等长呢?我们看下图,若此时,以i为中心的回文串(记为紫色)和以j为中心的回文串(记为红色)等长,那么两段绿色的字符也肯定相同,那么以pos为中心的回文串最右就不是到r了呀!

8.PNG

所以此时两段绿色内的字符一定不同,固以i为中心的回文串的最右只能到r。

2.i>r 也就是说,i在 以 pos 为中心的回文串外;

那么此时,我们就已经没有参照的j之类了,这时只要老老实实的向左右两边拓展就好了。

总的复杂度为O(n)。

代码实现

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
char s[12000000],now[24000000];
int i,j,k,m,n,len,pos,r,ma;
int p[24000000];
int my_min(int x,int y)
{
    return x<y?x:y;
}

int my_max(int x,int y)
{
    return x>y?x:y;
}

int manacher(char *s)
{
    for(int i=1;i<=len;i++)
    {
        now[i*2-1]='%';
        now[i*2]=s[i];
    }//进行操作一,插入%

    len=len*2+1;now[len]='%';
    pos=0;r=0;//初始化pos,r

    for(int i=1;i<=len;i++)
    {
        if(r>=i)p[i]=my_min(p[2*pos-i],r-i);//情况1;
        else p[i]=1;
        while(1<=i-p[i] && i+p[i]<=len && now[i-p[i]]==now[i+p[i]])p[i]++;//应对情况2,向两边拓展
        if(i+p[i]>r)
        {
            r=i+p[i];
            pos=i;
        }
        ma=my_max(ma,p[i]-1);
        //更新r,pos,最长回文串长度ma
    }
}
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);ma=0;
    manacher(s);
    printf("%d",ma);
    return 0;
}

结语

通过这篇博客,相信你已经学会了Manacher,感兴趣的同学可以去Luogu p3805完成这道模板题,运用Manacher,速度也相当可观。

9.PNG

希望你喜欢这篇Blog!

Last modification:July 12th, 2018 at 05:25 pm
If you think my article is useful to you, please feel free to appreciate