Manacher算法_马拉车图

全栈程序员站长

发布于 2022-11-01 12:58:07

1360

发布于 2022-11-01 12:58:07

文章被收录于专栏：全栈程序员必看

大家好，又见面了，我是你们的朋友全栈君。

参考：https://www.cnblogs.com/xiuyangleiasp/p/5070991.html

先了解下数组P[i]，id，mx的含义，下面的红字部分

Manacher算法利用一个辅助数组P[i]表示以字符Str[i]为中心的最长回文子串的最右（左）字符到Str[i]的距离（包括Str[i]）

以abbc为例，首先预处理变成：$#a#b#b#c# (预处理是为了便于处理）可以发现经过预处理后以字母为中心的最长回文串的长度都为奇数

因为字母两边的都是#。

i 0 1 2 3 4 5 6 7 8 9

str	$	#	a	#	b	#	b	#	c	#
p[i]	1	1	2	1	2	3	2	1	2	1

以这段来说

对于中间的#来说，最长回文串到中点#（包括中点的长度）的长度为3，即上面有颜色的部分的长度，即p【5】=3

同时也可以发现

P数组有一个性质：P[i]-1是该回文子串在原来字符串中的长度。

例如对于上面中#b#b#这段，这段以中间的“#”为中心，p[5]=3,p[5]-1=2,恰好是bb的长度

假如我们知道p[i]数组，进而求得最大值，然后-1就是该字符串的最长回文串了。接下来是P数组的计算

P数组的计算

如何计算P[i]呢？首先从左至右依次计算P[i]，但计算P[i]时，P[j](j<i)已经计算完毕。增加两个辅助变量id和mx，其中id表示最大回文子串中心的位置，mx=id+P[id]，即回文子串的边界。

由于P[i]数组是从左往右遍历，这里我们必须得理解id和mx的含义。这里在强调下这三个含义

id表示最大回文子串中心的位置 mx=id+P[id]，即回文子串的边界 P[i]表示以字符Str[i]为中心的最长回文子串的最右(左）字符到Str[i]的距离（包括Str[i]）

我们先理解下：已知下图中i-6~i是以id为中心的最长回文子串，也就是说str【i-7】！=str【i+1】；根据mx=id+P[id]，id指向i-3，由于P[i]表示以字符S[i]为中心的最长回文子串的最右（左）字符到S[i]的距离（包括S[i]），所以P[id]=4，即id+P[id]=4+（i-3）=i+1；即mx指向i+1，可以看出mx指向的位置并不在以id为中心的最长回文串中，同时mx与mx的对称点指向的字符是不相等的

当我们遍历到 i 时，

由于mx指向的位置并不在以id为中心的最长回文串中，所以可以对i与mx的比较分成两种情况讨论，

一种是i在回文串中的情况，即i<mx；

另一种是i不在回文串中的情况，即i>=mx

i<mx

令j=2*id-i，即j为i关于id的对称点。可以对照上图中，id=i-3，i关于id的对称点是i-6，就满足i-6==2*id-i;

由于是从左往右计算p[i],故此时p[ j ]已经计算好了，现在要做的事情是如何利用已经算好的p[ j ] 来更新p[ i ]，从而提高效率。

首先我们需要一个参照量,它的含义是表示从i到以id为中心的最长回文串右边界的长度（包括i这个点），mx表示的是右边界，上面已经提到mx指向的字符不在以id为中心的回文串中，长度就是： i+1到mx-1这段的长度(含两端)+中点i =（mx-1-（i+1）+1）+1 =mx-i

现在就是将p[ j ]与这个参照量 mx-i 相比较

当P【 j 】>mx-i时，说明以 j 为中心的回文字串有部分超出了以id为中心的回文子串，而超出的部分（下图中的1部分）关于id的对称部分（下图中4部分）必定>=mx,，可知1,2,3部分都对应相等，而之前讲过mx与mx的对称点指向的字符是不相等的，说明1与4部分不对应相等，所以我们所能确保的是以i为中心，P【i】至少为mx-i （为什么说是至少呢，因为p[ j ]已经帮了很大的忙了，剩下的只能靠我们自己朝两端遍历（下面会讲））

当P【 j 】<=mx-i 时，以Str[j]为中心的回文子串全包含在以Str[id]为中心的回文子串中，基于对称性可知，即下图中颜色相同的对称相等，所以P【i】=P【j】=P【2*id – i】

综上所述，可以得出结论：如果i<mx，则P[i]至少等于min(P[2*id-i],mx-i)。这里是将上面两种情况放在一起考虑，然后在向两边延伸判断（就是下面while语句）。（当然也可以将上面的两种情况分开讨论，可以发现情况二P【 j 】<=mx-i 是不需要向两边延伸判断的。这里将这两种情况放在一起是为了简便些。）

i>=mx

如果i比mx大，则说明对于以S[i]为中心的回文子串还有一部分没有匹配，由于无法对P[i]做更多的假设，只能先令P[i]=1，然后在后续进行相关匹配。

——–

i<mx和i>=mx两种情况用代码实现：

if(mx>i)
     p[i]=min(p[2*id-i],mx-i);
else
     p[i]=1;

Jetbrains全家桶1年46，售后保障稳定

以i为中心向两端延伸判断:然后以i中心，往两边延伸，直到两边对称的字符不相等；由于之前以算出i-P【i】+1到i+P【i】-1这段已是回文字串，只需从i-P【i】向左，i+P【i】向右

用代码实现：

while(str[i-p[i]]==str[i+p[i]]) p[i]++;

最后更新mx与id，若i+P[i]>mx,说明以i为中心的回文字串超过的边界mx，就需要更新

实现代码：

if(i+p[i]>mx)
{
    mx=i+p[i];
    id=i;
}

这样P【i】数组就求出来了

完整代码

#include<cstdio>
#include<iostream>
#include<cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
char str[2010];
int p[2500];
int main()
{
	while(scanf("%s",str)==1)
    {
        int len=strlen(str);
        memset(p,0,sizeof(p));
        //预处理
        for(int i=len;i>=0;i--)
        {
            str[2*i+2]=str[i];
            str[2*i+1]='#';
        }
        str[0]='$';
        int mx=0;
        int id=0;
        int res=0;
        for(int i=0;i<=2*len+1;i++)
        {
            if(mx>i)
                p[i]=min(p[2*id-i],mx-i);
            else
                p[i]=1;
            while(str[i-p[i]]==str[i+p[i]]) p[i]++;
            if(i+p[i]>mx)
            {
                mx=i+p[i];
                id=i;
            }
        }
        //输出P数组
        for(int i=0;i<=2*len+1;i++)
            printf("%d ",p[i]);
        printf("\n");

    }
	return 0;

}