β

Manacher's algorithm:优雅的求最长回文子串

Come on, man 836 阅读
 

2015年第一篇文章,力求做到用中文把 Manacher’s算法 解释的通俗易懂。

历史&背景

Manacher’s算法是Manacher在1975年提出的一个在线性时间里找出给定字符串中全部回文子串的算法,随着人们的研究,人们发现Manacher’s算法也可以用来求给定字符串的 最长 回文子串,当然也是线性时间。再后来,有两个小伙提出了基于suffix trees的算法,同样是线性时间求解最长回文子串,慢慢地,人们又找到了一些高效的并行算法求解这类问题。

本文将阐述Manacher’s算法用于求解给定字符串的最长回文子串,样例代码使用Python。

算法

Manacher’s算法真的很简单,你只要静下心来,花二十分钟来阅读并理解以下文字,绝对可以理解,理解了就一辈子都忘不了,接着你会暗暗叫绝,这算法真太赞了。相信你在看到本文之前也看了很多其他的文章,为了减少读者的理解障碍,使用的变量名称我都会尽量跟其他文章的一样。

预处理


为了将最长子串长度为奇数和偶数这两种情况统一转成奇数情况处理,Manacher’s算法在输入字符串的每个字符之间加了一个特殊字符;

为了简化处理过程中遍历字符串时对边界条件的判断,在开头加上另一个特殊字符,这些特殊字符要保证不会出现在任何输入字符串里,见下图:

manacher_5

准备工作


OK,下面是理解这个算法的过程中,要 随时装在脑子 里的一些东西:

manacher_4

高能预警


上面的你都理解了,那么我们看算法的精髓部分,静下心。

首先介绍一下变量,仔细阅读,很重要,下面的叙述是基于这些变量的:

manacher_1

OK,初始假设 current_longest_p_str 的中心字符是 s[0],也即 center=0,且假设 p[0]=0。

从 s[1] 开始遍历 s(略过我们为了处理边界在开头加的特殊字符),对 s[i],分两种情况来看:

情况1

s[i] 在 current_longest_p_str 内(如果在的话,可以进一步得出,s[i] 一定在其右半部分,因为是按顺序遍历s,i一定大于center)。

记i关于center的对称点为j(别忘了 j = 2 * center - i

此时,如果 i + p[j] < mx 的话,等价于 j - p[j] > mx的对称点 ,意味着,以 s[j] 为中心的最长回文串完完整整的在current_longest_p_str内,根据current_longest_p_str的对称性,可得以s[i]为中心的最长回文串也完完整整的在current_longest_p_str内,因此 p[i]=p[j] 成立,见下图:

manacher_3

如果 i + p[j] >= mx 的话,意味着,以 s[j] 为中心的最长回文串的一部分在 current_longest_p_str 内。根据 current_longest_p_str 的对称性我们可以知道,以 s[i] 为中心的最长回文子串,至少可以延展到 mx。那 mx 之后的部分呢?由于 mx 之后的字符串我们没办法利用 current_longest_p_str 的对称性了,没办法,只能一个一个去匹配了。转到代码上就是我们可以把 p[i] 置为 mx - i,也即我们已经知道s[i]向右可以扩展到 mx 了(下图橙色框起来部分),再根据逐步向两侧扩展的情况去更新 p[i] 。见下图。

manacher_2

综合以上两种情况,可以得出 p[i] = min(p[j], mx - i) ,也即 p[i] = min(p[2 * center - i], mx - i)

情况2

s[i]不在 current_longest_p_str 中,没办法利用 current_longest_p_str 的对称性,只能先将 p[i] 置为0,再向两侧扩展一个一个匹配来更新 p[i] 了。

代码

class Solution:
def pre_process(self, s):
return "".join(("$#", "#".join(s), "#"))

# @return a string
def longestPalindrome(self, s):
s_new = self.pre_process(s)
p = [0]
center = 0
mx = 0
for i in range(1, len(s_new)):
# 情况2,s[i]不在current_longest_p_str中
if i > mx:
p.append(0)
# 情况1,s[i]在current_longest_p_str中
else:
p.append(min(mx - i, p[2 * center - i]))
# 没办法,只能一个一个去匹配了
# 注意,对于以s[i]为中心的最长回文子串完完整整包括在current_longest_p_str的情况,while循环不会执行,想想为什么
while (i - p[i] - 1) > 0 and (i + p[i] + 1) < len(s_new) and s_new[i - p[i] - 1] == s_new[i + p[i] + 1]:
p[i] += 1
# 更新current_longest_p_str相关信息
if p[i] > mx - center:
center = i
mx = i + p[i]
return s_new[center - p[center]: center + p[center] + 1].replace("#", "")

后记

希望能给你带来一点帮助,如有理解错误,恳请指正。

参考文献

2015年第一篇文章,力求做到用中文把 Manacher’s算法 解释的通俗易懂。

 
作者:Come on, man
liushuaikobe
原文地址:Manacher's algorithm:优雅的求最长回文子串, 感谢原作者分享。