MENU

回文数算法之马拉车算法

April 4, 2020 • Read: 484 • 算法

由于第一次写解析的时候表述不清晰,这次我尽力写的易懂点
update time:2020,2,21

我先用一个题目引入今天要讲的算法:

NOJP2132

看到的题目,你的脑中一定会有很多想法,比如使用暴力算法,找出里面一共有多少个子串,然后挨个来判断是否为回文数,又或许使用动态规划来解决这个题,又或者使用中心检测法……

作为一个力扣异教徒,我决定使用马拉车算法来解决这个题,力扣原题:P647 回文子串

但是这些算法所需要的时间都略长,我不敢保证马拉车算法是最简单的(他当然不简单),但我能保证马拉车算法一定不会慢

什么是马拉车算法?

1975年,Manacher发明了Manacher Algorithm算法,俗称马拉车算法,这种算法能利用回文数的特性避免重复计算,该算法的时间复杂度仅仅只有O(n)

下面我来解释一下这项神奇的算法:

1.处理字符串

使用马拉车算法的第一步,就是处理字符串,因为字符串的长度可能为奇数,也可能为偶数,这样就会导致这个算法得分成两种情况处理,为了避免出现这种情况,我们就应当先处理字符串,使奇数长度的字符串和偶数长度的字符串能用相同方案解决

我们先来看两个例子:

“abcd”,这是一个偶数长度的字符串,我们再字符串的字符间隙中先插入“#”,然后再在开头和结尾分别插入“@”,“&”,然后我们便可以得到一个新的字符串“@#a#b#a#b#&”,他的长度为11,是一个奇数长度的字符串

“abc",这是一个奇数长度的字符串,我们按照相同的方法处理他,就得到了新的字符串"@#a#b#c#&”,长度为9,也是一个奇数长度的字符串

2.计算最长回文子串数组P

这里先解释几个专有名词

1.回文半径是什么?

答:回文数最右端边界到回文数对称轴的长度,表示为 r-i

2.什么是最长回文子串数组P

答:在计算最长回文数组的时候,我们需要计算每一个子回文数组的最大长度,为了避免重复计算,我们可以将改造后的T[i]的回文半径存储到数组P[]中,P[i]即为新字符串T在以i为中心的最长回文的半径了,P[i]表示以字符T[i]为中心的最长回文字串的最端右字符到T[i]的长度,如以T[ i ]为中心的最长回文子串的为T[ l, r ],那么P[ i ]=r-i,若P[ i ]=1表示该回文串就是T[ i ]本身,由这些元素组成的数组便是回文子串数组

下面我用字符串“ababa”举个例子:

index0123456789101112
T@#a#b#a#b#a#@
P0010305030100

数组P有一个性质,P[i]就是该回文子串在原字符串中的长度,证明:

首先在转换得到的字符串T中,所有的回文字串的长度都为奇数,那么对于以T[i]为中心的最长回文字串,其长度就为2*P[i]+1,经过观察可知,T中所有的回文子串,其中分隔符(不计算@)的数量一定比其他字符的数量多1,也就是有P[i]+1个分隔符,剩下P[i]个字符来自原字符串,所以该回文串在原字符串中的长度就为P[i]

3.如何计算数组P

我们首先观察一下数组P,可以很清晰的发现他们的值是关于6号位对称的,这当然不是巧合,这是回文串的性质之一,由于证明比较简单,具体怎么证明我想我不比多言了。

从左往右计算数组P[],我们需要分多种情况来解决这个问题(说明:灰色边界到j就是P[j])

i和j相对称,所以j=2*Mi-i

8uv8US.png

  1. 当i<=R,并且P[j]<R-i 时,说明以点j为中心的回文串并没有超出范围[L,R],则由回文串的特性可以得知:P[i]=P[j]

8uvduq.png

b.当i<=R,并且P[j]>=R-i,即如上图所示,当我们还以为P[i]=P[j]的时候,问题出现了,如果P[i]=P[j],那么是不是P[L-1]=P[R+1]呢?这很显然是不对的,因为R和L分别是以Mi为中心的回文字符串的最大回文边界,如果P[L-1]=P[R+1],那么L和R便不再是最大回文边界了,出现了矛盾点,所以P[L-1]必不可能等于P[R+1],对于这种情况,我们还是只能从R+1开始一 一匹配,知道失配为止,从而更新R和对应的Mi以及P[i]

8uvo5D.png

c.当i>R时,此时我们无法再利用回文串的特性,只能老老实实的一步步取匹配

3.总结一下这个算法

  1. 处理字符串
  2. 分情况制作P数组
  3. 遍历P数组,计算结果

为了便于理解,这里先拿出一份Python代码,看不懂的同学忽略即可:

S="ababa"
#初始字符串
A = '@#' + '#'.join(S) + '#$'
Z = [0] * len(A)
print(list(A))
#处理字符串并输出
center = right = 0
for i in range(1, len(A) - 1):
    if i < right:
        Z[i] = min(right - i, Z[2 * center - i])
        #2 * center - i对应的是j的位置
    while A[i + Z[i] + 1] == A[i - Z[i] - 1]:
        Z[i] += 1
        #对应第二种情况
    if i + Z[i] > right:
        center, right = i, i + Z[i]
        #移动对称中心
print(Z)
print(sum((v+1)//2 for v in Z))

这里拿出大家都看得懂的cpp代码:

#include<bits/stdc++.h>
using namespace std;
int Z[5005];
int main(){
    string str1;
    while(cin>>str1){
        memset(Z,0, sizeof(Z));
        string A="@#";
        for (int i=0;i<str1.length();i++){
            A+=str1[i];
            A+="#";
        }
        A+="$";
        int center=0,right=0;
        for (int i=1;i<A.length()-1;i++){
            if (i<right)
                Z[i]=min(right-i,Z[2*center-i]);
            while (A[i+Z[i]+1]==A[i - Z[i] - 1]){
                Z[i]++;
            }
            if (i + Z[i] > right) {
                center = i;
                right = i + Z[i];
            }
        }
        int ans=0;
        for (int x=0;x<A.length();x++){
            ans+=(Z[x]+1)/2;
        }
        cout<<ans<<endl;
    }

    return 0;
}
Last Modified: April 18, 2020
Archives Tip
QR Code for this page
Tipping QR Code