回文字符串算法

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

Python 实现各种常用算法 – 字符串 – 实验楼
 

所谓回文字串，即正着读和倒着读结果都一样的字符串，比如:a, aba, abccba 都是回文串, ab, abb, abca 都不是回文串。

暴力求解的思路：找到字符串的所有子串，遍历每一个子串以验证它们是否为回文串。一个子串由子串的起点和终点确定，因此对于一个长度为 n 的字符串，共有 n^2 个子串。这些子串的平均长度大约是 n/2，因此这个解法的时间复杂度是 O(n^3)。我们能不能提高效率呢，当然可以。这里给大家介绍马拉车算法。

求解回文串的问题，有很多巧妙的求解算法，这里仅介绍马拉车算法，其他求解算法无法一一介绍，感兴趣的同学请自行探索。

马拉车算法

马拉车算法(Manacher)由一个叫 Manacher 的人在 1975 年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性，这是非常了不起的。让我们来看下马拉车算法的优越性在哪。

(1) 解决长度奇偶性带来的对称轴位置问题

Manacher 算法首先对字符串做一个预处理，在所有的空隙位置(包括首尾)插入同样的符号，要求这个符号是不会在原串中出现的。这样会使得所有的串都是奇数长度的（奇数会插入偶数个#号，偶数插入奇数个#号）。以插入#号为例：

aba->#a#b#a#

abba->#a#b#b#a#

插入的是同样的符号，且符号不存在于原串，因此子串的回文性不受影响，原来是回文的串，插完之后还是回文的，原来不是回文的，依然不会是回文的。

(2) 解决重复访问的问题

我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为回文半径。Manacher 定义了一个回文半径数组 RL，用 RL[i]表示以第 i 个字符为对称轴的回文串的回文半径。我们一般对字符串从左往右处理，因此这里定义 RL[i]为第 i 个字符为对称轴的回文串的最右一个字符与字符 i 的距离。对于上面插入分隔符之后的两个串，可以得到 RL 数组。

char:    # a # b # a #
RL  :    1 2 1 4 1 2 1
RL-1:    0 1 0 3 0 1 0
i   :    0 1 2 3 4 5 6

char:    # a # b # b # a #
RL  :    1 2 1 2 5 2 1 2 1
RL-1:    0 1 0 1 4 1 0 1 0
i   :    0 1 2 3 4 5 6 7 8

上面我们还求了一下 RL[i]-1。通过观察可以发现，RL[i]-1 的值，正是在原本那个没有插入过分隔符的串中，以位置 i 为对称轴的最长回文串的长度。那么只要我们求出了 RL 数组，就能得到最长回文子串的长度。

于是问题变成了，怎样高效地求的 RL 数组。基本思路是利用回文串的对称性，扩展回文串。

我们再引入一个辅助变量 MaxRight，表示当前访问到的所有回文子串，所能触及的最右一个字符的位置。另外还要记录下 MaxRight 对应的回文串的对称轴所在的位置，记为 pos，它们的位置关系如下。

我们从左往右地访问字符串来求 RL，假设当前访问到的位置为 i，即要求 RL[i]，在对应上图，i 必然是在 po 右边的(obviously)。但我们更关注的是，i 是在 MaxRight 的左边还是右边。我们分情况来讨论。

1） 当 i 在 MaxRight 的左边

我们知道，图中两个红色块之间（包括红色块）的串是回文的；并且以 i 为对称轴的回文串，是与红色块间的回文串有所重叠的。我们找到 i 关于 pos 的对称位置 j，这个 j 对应的 RL[j]我们是已经算过的。根据回文串的对称性，以 i 为对称轴的回文串和以 j 为对称轴的回文串，有一部分是相同的。这里又有两种细分的情况。

a.以 j 为对称轴的回文串比较短

这时我们知道 RL[i]至少不会小于 RL[j]，并且已经知道了部分的以 i 为中心的回文串，于是可以令 RL[i]=RL[j]。但是以 i 为对称轴的回文串可能实际上更长，因此我们试着以 i 为对称轴，继续往左右两边扩展，直到左右两边字符不同，或者到达边界。

b.以 j 为对称轴的回文串比较长

这时，我们只能确定，两条蓝线之间的部分（即不超过 MaxRight 的部分）是回文的，于是从这个长度开始，尝试以 i 为中心向左右两边扩展，，直到左右两边字符不同，或者到达边界。

不论以上哪种情况，之后都要尝试更新 MaxRight 和 pos，因为有可能得到更大的 MaxRight。

具体操作如下：

1. 令 RL[i]=min(RL[2*pos-i], MaxRight-i)
2. 以 i 为中心扩展回文串，直到左右两边字符不同，或者到达边界
3. 更新 MaxRight 和 pos

2) 当 i 在 MaxRight 的右边

遇到这种情况，说明以 i 为对称轴的回文串还没有任何一个部分被访问过，于是只能从 i 的左右两边开始尝试扩展了，当左右两边字符不同，或者到达字符串边界时停止。然后更新 MaxRight 和 pos

在 /home/shiyanlou/ 下新建一个文件 manacher.py。

参考代码如下；

def manacher(s):
    # 预处理
    s = '#'+'#'.join(s)+'#'

    RL = [0]*len(s)
    MaxRight = 0
    pos = 0
    MaxLen = 0
    for i in range(len(s)):
        if i < MaxRight:
            RL[i] = min(RL[2*pos-i], MaxRight-i)
        else:
            RL[i] = 1
        # 尝试扩展，注意处理边界
        while i-RL[i] >= 0 and i+RL[i] < len(s) and s[i-RL[i]] == s[i+RL[i]]:
            RL[i] += 1
        # 更新MaxRight,pos
        if RL[i]+i-1 > MaxRight:
            MaxRight = RL[i]+i-1
            pos = i
        # 更新最长回文串的长度
        MaxLen = max(MaxLen, RL[i])
    return MaxLen-1