Manacher 算法是一位名叫 Manacher 的大佬在 1975 年发现的求最长回文子串的算法,由于网上没有找到资料,所以就不用介绍这位大佬了。Manacher 算法的时间复杂度是 O(n),感觉很精妙,于是写下这篇文章记录一下自己的理解。

最长回文子串

求最长回文子串是一道经典的算法题。回文串就是翻转之后和原字符串一样的串,比如神车(雾)思域的英文 civic 就是一个回文串,回文中心是字符 v;单词 noon 也是回文串,不过这种偶数串没有一个具体的字符作为回文中心。

在讨论 Manacher 算法之前,我们先来看两种比较容易想到的解法。

解法一:暴力法

列出字符串的所有子串,判断是不是回文串,然后找到最长的那个。这个解法过于暴力,粗略来看,求所有子串的花费是O(n^2),判断每个子串的花费是O(n),所以整体时间复杂度是O(n^3)。
其中有大量可以优化的重复计算,比如:

  • 如果一个子串不是回文串,那么以它为中心的所有子串都不是回文串
  • 如果已经找到一个长度为n的回文子串,那么所有长度小于n的子串都没必要再判断
    等等

所以很明显这不是一个好的解法。

解法二:中心扩展法

中心扩展法的思路是遍历字符串,以每个字符为中心,逐渐向外扩展,判断两侧的字符是否相等,如果相等就是回文串,继续向外扩展,直到字符不再相等,这样就得到了一个以这个字符为中心的最长回文串。
找到每个字符作为回文中心的最长回文串后,比较得出最长的解。

比如求 abcbe 的最长回文子串,逐个字符遍历:

回文中心 最长回文串
a a
b b
c bcb
b b
e e

遍历完之后,发现以c为回文中心的回文子串 bcb 是最长的。

有一个细节要注意。可能你已经发现上面以5个字符作为回文中心,得出最优解是 bcb 可能是有问题的。因为以字符作为回文中心,考虑的都是奇数串的解,忽略了所有可能的偶数串解。比如,对于 abacca 这个字符串,以字符作为回文中心得到的最长回文串是 aba,但其实最长的串是 acca。
所以中心扩展的时候,既要以字符为回文中心,也要以字符间的间隔作为回文中心。即遍历到第 i 个字符时,既要以 i 为中心,向i-1/i+1、i-2/i+2这样扩展,也要以 i 和 i+1 之间的间隔为中心,向 i/i+1、i-1/i+2 这样扩展。

我觉得中心扩展法最符合常人的思路,比较容易理解。因为遍历字符串的花费为O(n),求每个字符为中心的最长回文串的花费是O(n),所以时间复杂度是O(n^2)。

Manacher 算法的思想

我想把 Manacher 算法理解成基于上面中心扩展法的优化,优化点有两个,理解了这两个优化点,也就理解了 Manacher 算法。

第一个优化点

上面提到中心扩展法要按奇偶考虑不同的回文中心,这在处理起来有一些麻烦的。
而 Manacher 算法的第一步操作就是抹平这种奇偶之间的差异——在首尾以及所有字符之间插入一个特殊符号(#)。比如对于 abcba 和 abba 两个回文串,插入 # 后变成 #a#b#c#b#a#和#a#b#b#a#,两个都变成奇数串,第一个回文中心还是 c,第二个回文中心是 #。


(处理之后的回文串,红框表示回文中心。可以看到,偶数串在经过处理后,也有了一个真实的回文中心。)

这是 Manacher 算法一个很有意思的地方。是不是很好理解?那么可以继续啦。

第二个优化点

第二个优化点是 Manacher 算法的核心,避免了大量的重复计算,保证了 O(n) 的时间复杂度。

我们先来看一个栗子,求字符串 aabcbebcbabcba 的最长回文子串。(为了简化,我们先忽略掉偶数串的解以及插入 # 的操作。)对于这个字符串,使用中心扩展法逐个字符求解,一共需要求出 14 个解(如表格所示)。得到最长的解是以 e 作为回文中心的 abcbebcba(表格中的标红部分)。

索引 字符 最长回文串 回文半径
0 a a 0
1 a a 0
2 b b 0
3 c bcb 1
4 b b 0
5 e abcbebcba 4
6 b b 0
7 c bcb 1
8 b b 0
9 a bcbabcb 3
10 b b 0
11 c abcba 2
12 b b 0
13 a a 0

仔细观察 abcbebcba 这个超长回文串,在回文中心 e 两侧,各字符的最长回文串是一致的(表格中标黄部分)。因为回文字符串本身就是左右对称的,比如左侧出现 bcb,右侧必然也会出现一个 bcb,不然就左右不对称,整个串就不是回文字符串了。

理解了这一点,也就理解了 Manacher 算法的核心。没错, Manacher 算法就是要针对右侧的字符,尽量去避免计算这些字符的回文串。

为了方便说明,我们把字符串记为 s,s[0] 代表字符 a,s[1] 代表 a,s[2] 代表 b……。

在回文中心 s[5](字符 e)的两侧,每个字符以及字符作为回文中心的回文串,都是对称的。我们再来仔细看一下,s[4] 和 s[6] 对应字符都是 b,回文串都是 b,s[3] 和 s[7] 对应的字符都是 c,回文串都是 bcb。这样来看,对于 s[5] 右侧的 s[6]、s[7],确实没有必要求解,直接去找 s[4]、s[3] 就可以。

回文半径

这里说明一下,Manacher 算法并不求每个字符对应的回文串,而是求每个字符对应的回文串的回文半径(回文半径可以理解成回文串单侧字符的个数,回文半径越大回文串越长。上面的表格也记了回文半径一列。我们这里把单个字符的回文半径约定是0,当然也可以约定是1,不影响),最终得到一个回文半径数组。回文半径最大的字符,当然拥有最长的回文串。

为了方便说明,我们把回文半径数组记为 p,p[0] 表示第 0 个字符的回文半径,值是0,p[5] 表示第5个字符的回文半径,值是4……。
这样就是,p[6] 和 s[4] 相等,都是0,p[7] 和 p[3] 相等,都是3。p[8] 和 p[2] 相等,都是2。


https://raw.githubusercontent.com/JeremyFan/static/images/blogs/manacher/manacher_1.jpeg

例外情况

等等,好像 p[9] 并不等于 p[1]?

其实也很好理解,abcbebcba 这个超长回文串有范围的,范围可以理解成回文串最远处字符的索引。只有在回文串的范围内,字符才是确定的、可以预期的。比如这里 abcbebcba 最远处的索引是 9,s[9] 在最边缘,超出部分的字符是无法预期的,所以不能直接认为 p[9] 和 p[1] 相等:s[0] 和 s[2] 不相等,p[1] 是 0,但说不定 s[10] 和 s[8] 相等呢。如果 s[10] 和 s[8] 相等,p[9] 就至少是 1 了;如果 s[11] 和 s[7] 也相等,p[9] 就至少是 2 了……

嗯又回到了中心扩展法,如此一步一步试探,最终可以得出 s[9] 的回文半径是 3,不小呢。

有了这个 s[9] 作为回文中心的回文串 bcbabcb,最远处字符的索引是 12,于是这个范围内的部分字符也就不用再求回文半径了(功能相当于之前 s[5] 对应的回文串)。
p[10] 直接等于 p[8]。p[11] 要注意一下,p[7] 值是 1,p[11] 至少可以是1了,此时回文半径也到达了范围边界,然后用中心扩展法试探 s[13] 和 s[9] 相等,s[13] 已经是字符串最后一个字符,所以 p[11] 的值是2。

Manacher 算法就是这样不断利用已知的回文半径,求解其他字符的回文半径。所有字符求解完后,自然就得出回文半径数组了。
找到回文半径数组中最大的那个元素,再结合半径,就可以截取到最长的回文子串。

准备写码

为了把上面的理论转换成数学式,我们先来准备一些变量。

  1. 当前回文串的回文中心(即上面的 s[5]、s[9])的索引。因为只有知道中心的索引,求解右侧字符的时候,才能和左侧对应上。比如s[5]作为回文中心时,右侧 s[6] 对应的左侧的点是 s[4],对应的回文半径就是 p[6] 和 p[4]。如果我们把回文中心的索引记为变量 c ,求解右侧字符回文半径 p[i] 的时候,找对应左侧字符的回文半径 p[2*c - i] 就可以了。
  2. 当前回文串的范围(最远处的索引),这样才能知道求解右侧字符的时候是否需要用中心扩展法。按照上面的结论,求解右侧字符的回文半径,如果这个右侧字符的索引加上对应的左侧字符的回文半径还没有超过范围的话,就可以直接使用左侧字符的回文半径。如果把最远处的索引记为 mx,那么当 p[2c - i] < mx - i 时,p[i] = p[2c - i]。如果超出范围,至少范围内确定是回文串,回文半径至少可以从当前索引到范围,即当 p[2c - i] >= mx - i 时, p[i] = mx -i。综合起来就是 p[i] = Math.min(p[2c - i, mx- i])。
  3. 另外设置两个辅助变量 pm、pi,不涉及核心逻辑,记录目前拥有最大回文半径的字符、以及字符对应的索引,方便后续截取这个最长回文子串。

完整代码

最后附上完整的 JavaScript 实现:

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
function manacher(s) {
// 处理 s
var s2 = `#${s.split('').join('#')}#`

var mx = 0, // 回文串范围(最远处索引)
c = 0, // 回文串中心
p = [], // 回文半径数组
pm = 0,// 回文半径最大值
pi = 0 // 回文半径最大字符的索引

for (let i = 0; i < s2.length; i++) {
if (mx > i) {
p[i] = Math.min(p[2 * c - i], mx - i)
} else {
// 单个字符的回文半径认为是0
p[i] = 0
}

// 中心扩展法求回文半径,针对超出回文范围的情况:
// 1. i点本身超出mx范围
// 2. i点加上对称点的回文半径超出mx范围
while ((i - p[i] - 1 >= 0) && s2[i + p[i] + 1] === s2[i - p[i] - 1]) {
p[i]++
}

// 经过中心扩展法探测后,更新回文串的范围和回文中心
if (i + p[i] > mx) {
mx = i + p[i]
c = i
}

// 记录一下拥有最大回文半径字符的位置,方便后面取子串
if (p[i] > pm) {
pm = p[i]
pi = i
}
}

// 取子串
return s2.slice(pi - pm, pi + pm + 1).split('#').join('')
}
console.log(manacher('abcba'))
console.log(manacher('cbcdcbe'))

总结

  1. 无论长度为奇数还是偶数的字符串,每个字符中间插入一个特殊字符,得到新的字符串长度都是奇数。这样处理后,字符串里的每个回文子串,都有一个确定的字符作为回文中心。
  2. 整体求的是一个回文半径数组,需要每一个字符的回文半径。回文半径最大的字符就是最终解最长回文子串的回文中心。
  3. 求到某个字符的回文半径后,根据回文串的对称性,半径范围内右侧字符的回文半径等于对应的左侧字符的回文半径。
  4. 如果某个右侧字符超出范围(字符本身在半径最边缘;或加上左侧对应字符的回文半径后在最边缘),就使用中心扩展法探测出这个字符的回文半径。
  5. 重复3、4直到求出最后一个字符的回文半径。

参考资料