回文数算法之马拉车算法

由于第一次写解析的时候表述不清晰，这次我尽力写的易懂点
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”举个例子：

index	0	1	2	3	4	5	6	7	8	9	10	11	12
T	@	#	a	#	b	#	a	#	b	#	a	#	@
P	0	0	1	0	3	0	5	0	3	0	1	0	0

数组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

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

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]

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;
}