求最长回文子串——ManaCher算法

0.问题定义

最长回文子串：求任一既定字符串中，回文子串的最长长度

• 回文：正向和反向完全一样的字符串叫做回文字符串
• 子串：从一个字符串中任意截取一段是这个字符串的子串

1. 暴力破解法

这是最容易想到的办法。先遍历获得字符串的所有子串，再对每个子串判断其是不是回文串。

对于长度为n的字符串，子串个数为n(n-1)/2，加上对每个子串进行判断，这种解法的时间复杂度为O(n^3)。代码就不写了，下面重点介绍Manacher算法

2. ManaCher算法

由回文的定义可以推出回文串有轴对称的特性。所以可以从字符串的轴心点（可能是两个字符中间的空位）开始向左右两侧同时进行比较，一直找到两端不相同的字符为止，就是一个回文子串。

但这里存在一个问题，字符串的长度可能为奇数，也可能为偶数。轴心点的位置可能是字符串中的某个字符，也可能是相邻两个字符之间的空位。对于从轴心点开始向两侧寻找边界的方法来说，就需要对两种情况都进行考虑。

2.1 解决回文子串长度奇偶性问题

难道需要每个字符位遍历两次？ManaCher告诉你那个太复杂！ManaCher算法的第一个要点就是解决回文串长度奇偶性的问题。解决的方法很巧妙，在开始遍历之前先对母串进行预处理，在母串的首尾以及相邻两个字符之间插入一个母串中没有出现的字符。这样处理之后，所有的回文子串都会变为长度为奇数的回文串，也就是说，我们只需要以每个字符为轴心来考虑即可。

其实我的个人理解就是，通过插入字符将原本是中间空位的轴心转化为新字符串的一个字符

2.2 解决重复访问的问题

基于回文串的对称性性质，我们可以发现，有很多回文子串其实是更长的一个回文子串的子串，而且这种子串会在更长的回文串的轴心两侧对称出现。这种回文串显然不是问题需要的答案，但不对其进行处理会浪费遍历的时间。ManaCher算法根据回文串的对称性，对这种本质相同的回文串进行简化处理。

首先，定义了三个变量：

• 定义一个

  回文半径

  数组P。我们把一个回文串中最左或最右位置的字符与其对称轴的距离称为

  回文半径

  。 用P[i]表示以第i个字符为对称轴的回文串的回文半径。
• 辅助变量

  max_right

  ，表示当前访问到的所有回文子串，所能触及的最右一个字符的位置。
• 辅助变量

  center

  ，边界最靠右的回文串的对称轴所在的位置。有多个回文串最右边在同一位置时，选择轴心最靠左的记录

新字符串的

回文半径

就是原字符串的回文子串长度。那么只要我们求出了

P

数组，就能得到最长回文子串的长度。

我们从左往右地访问字符串来求

P

，假设当前访问到的位置为

i

，即要求

P[i]

1. 当

   i < max_right

   这就意味着位置为

   i

   的字符位于一个回文子串之中，这个回文子串的轴心是

   center

   ，回文半径为

   max_right - center

   。根据回文的对称性，可以得出一个公式：

   其中，

   P[2*center -i]<max_right-i

   的情况，

   p[i]

   是一定等于

   P[2*center -i]

   。但其他情况下并不能最终确定

   P[i]

   的值。怎么办？只能是按照对称性对比

   i

   两侧的字符，当然

   max_right - i

   这个半径内的字符是不需要再进行比较的！

   如果

   i+P[i]>max_right

   则要更新

   max_right

   和

   center

   :
2. 当

   i>= max_right

   此时，位置为

   i

   的字符位于已知的回文子串外部或者边界上，我们无法快速得知其回文半径，只能通过向两侧比较的方法。同样需要对

   max_right

   和

   center

   进行更新，不再重复

对预处理过的字符串从左到右按照以上步骤进行遍历之后，我们就得到了所有位置的回文半径数组

P

。求得其中最大值就是最长回文子串的长度了。

3. Python实现

由于最近在学习Python，所以用Python实现了一下ManaCher算法，代码如下：

#!/usr/bin/python3
# -*- coding: utf-8 -*-

DEBUG = 1

#对字符串进行插值，插入#


def insert(target):

    result = "*"
    for i in range(len(target)):
        result += "#" + target[i]

    result += "#$"
    if DEBUG:
        print(result)
    return result


def manacher(target):
    target = insert(target)
    max_right = 0  # 回文子串的最右边界
    center = 0  # 最右回文子串的轴心标记
    p = [0 for i in range(len(target))]  # 记录每个轴心的回文子串半径
    for i in range(2, len(target) - 2):
        if max_right > i:
            p[i] = min(p[2 * center - i], max_right - i)
        while target[i - p[i] - 1] == target[i + p[i] + 1]:
            p[i] += 1
        if i + p[i] > max_right:
            max_right = i + p[i]
            center = i
    if DEBUG:
        print("p=", p)
    return max(p)


if __name__ == '__main__':
    print(manacher('abc1234321ab'))
    print(manacher('asdflkjl'))
           

运行结果为：

*#a#b#c#1#2#3#4#3#2#1#a#b#$
('p=', [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 7, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0])
7
*#a#s#d#f#l#k#j#l#$
('p=', [0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0])
1