查找回文字符串：马拉车算法 Manacher's Algorithm

Posted on | In | views

在 LeetCode 看到一个题，给定一个字符串，返回最大长度的回文子字符串。

Example:

1
2
Input: "babad"
Output: "bab" or "aba"

最简单的方法就是暴力循环遍历，但是算法复杂度为 $O(n^3)$, 因此记录一个线性复杂度的算法——马拉车算法。

LeetCode：https://leetcode.com/problems/longest-palindromic-substring

英文解释：https://articles.leetcode.com/longest-palindromic-substring-part-ii

中文解释：https://www.felix021.com/blog/read.php?2040

Manacher’s Algorithm

首先，假设输入字符串为 abaaba，显然输入即为最长的回文字符串，因此输出应为 abaaba。让我们分两步来解决这个问题。

1. 预处理

我们想一下可能会发现，回文字符串分为两种情况：奇数长度和偶数长度。这两种情况显然是无法直接合并处理的，因此马拉车算法首先对输入的字符串进行了一下处理：在每个字符的两侧插入一个特定字符 #，例如：

1
2
S = 'abaaba'
T = '#a#b#a#a#b#a#'

这样做的好处是所有的字符串都变成了奇数长度，这样我们就不需要分别考虑了

预处理部分的代码如下：

1
2
3
4
5
6
def preProcess(self, s):
    l = [c for c in s]
    ret = '#'.join(l)
    
    # add ^ and $ at both bounds to avoid out of index problem
    return '^#'+ret+'#$'

2. 算法部分

算法的思想是这样的，对于一个预处理之后的字符串 T，定义一个具有相同长度的数组 P，使得 P[i] 等于以 T[i] 为中心的 T 中最长回文字符串的半径，对于上面的例子

1
2
T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

我们可以发现，P 具有某种对称性质，我们可以利用这个性质在一定程度上减小我们的计算复杂度。那么所有的情况都是对称的吗？可惜的是并不是，只有在某种特定的条件下这种情况才成立。但是没关系，我们一样可以利用这个性质减少计算，只是需要找到不满足这种情况的条件就可以了

我们来看一个稍微复杂一点的例子，S = ‘babcbabcbaccba’

上图中假设当前 i 为 13， 实线表示回文字符串 abcbabcba的中心，虚线表示两侧的边界。我们可以看到，由于回文字符串的对称性质，我们可以快速的知道 P[13] 的值，也就是等于 P[9] 处的值。然后继续看

现在我们到了下标为 15 的位置，p[15] 的值是多少呢？如果我们继续根据对称性质，那么就会得到 P[15] = P[7] = 7，但很显然是错误的。

如果以 T[15] 为中心，我们得到的回文字符串为 #a#b#c#b#a#，而 T[7] 处的回文字符串要更长，这是因为我们当前的以 C 为中心的回文字符串并不能完全包含以 T[7] 为中心的回文字符串，因此就造成了不满足对称性质的情况。解决办法也很简单，只要取 P[i] = min(P[i'], R-i) 就可以了。

用伪代码总结一下：

1
2
3
if P[i'] <= R - i
then P[i] = P[i']
else P[i] <= P[i']

然后我们需要确定 R 和 C 的更新策略：如果以 i 为中心的回文字符串的超过了 R，则令新的中心C = i，然后把 R 扩展到新的回文字符串的右边界。

全部代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        # Manacher's algorithm
        T = self.preProcess(s)
        length = len(T)
        C, R = 0, 0
        P = [0] * length
        i = 1
        while i < length-1:
            # i_mirror can reduce the computation of P[i]
            i_mirror = 2*C - i  # equals to C - (i - C)
            
            P[i] = min(P[i_mirror], R-i) if R > i else 0
            
            # expand the palindrome centered at i
            while T[i + P[i] + 1] == T[i - P[i] - 1]:
                P[i] += 1
            
            # adjust center if the expanded palindrome pasts R
            if R < i + P[i]:
                C = i
                R = i + P[i]
                
            i += 1
                
        maxLength = max(P)
        centerIndex = P.index(maxLength)
        
        start = (centerIndex - maxLength) // 2
        stop = start + maxLength
        
        return s[start:stop]
        
    def preProcess(self, s):
        l = [c for c in s]
        ret = '#'.join(l)
        
        # add ^ and $ at both bounds to avoid out of index problem
        return '^#'+ret+'#$'

最后

按理说线性复杂度的算法已经是很快了，当然 LeetCode 上还有很多大神的神仙代码更快，反正我是看不懂…… 🙂

完