最长回文子串(Manacher)算法朴实理解
今天找求解最长回文子串的算法，发现居然有O(n)复杂度的解法。必须找博客拜读一下。
然而大神们的博客都写得太学术了，欺负我智商低。像大唐白居易一样，写的诗老妪能解多好。(典故出自一些笔记小说，实际信不得的)
作为一个笨人，整理一个自己的朴实理解的版本，希望对大家有帮助。
预处理
假设有串S = “12321”，求他的最长回文子串。
首先在串的中间(包括首尾)加特殊字符，只要是串里本来没有的字符就行。于是
S = “#1#2#3#2#1#”
子串长度数组P
建立一个数组P，P和串S长度一样。P[i]的值就是以S[i]为中心的最长子串的半径。
举个栗子：
S = “# 1 # 2 # 3 # 2 # 1 #”
P = [0 1 0 1 0 5 0 1 0 1 0]
显然，最大的P[i]对应的S[i]的最大回文子串，就是要求的S的最大回文子串。
求解数组P
首先非常朴实的求解，也就是遍历S[i]的左右，看是否相等，得到以下结果。
S = “# 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 #”
P = [0 1 0 1 0 1 0 1 0 9 …]
算到这就可以偷懒了。
我们已经知道了以5为中心，左右9的范围，是一个回文子串，我们叫这个范围为已知范围。
考虑一下5右边的#，我们叫它"小右”，它在已知范围，最长回文子串长度未知。
考虑一下5左边的#，我们叫它"小左”，它在已知范围，最长回文子串长度已知。
“小右"和"小左"是对称的，它们的最长回文子串长度自然也是相同的。
所以 “小右"的最长回文子串长度不用算。 照抄"小左"的就行。
继续偷懒，得到以下结果。
S = “# 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 #”
P = [0 1 0 1 0 1 0 1 0 9 0 1 0 1 0 1 0 …]
偷懒这里要停一下了，即将计算1的最长回文子串长度。
如果继续偷懒，1还在已知范围，但1的最长回文子串边界和已知范围的边界有重合了。
在这种情况下就要朴实的计算1的最长回文子串。
S = “# 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 #”
P = [0 1 0 1 0 1 0 1 0 9 0 1 0 1 0 1 0 16 …]
现在已知范围更新为以1为中心的，左右16的范围了。然后又可以愉快的偷懒了。
重复这种朴实计算，然后偷懒，不能偷懒就朴实计算，然后再偷懒的过程，得到最终结果。
S = “# 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 # 2 # 3 # 4 # 5 # 4 # 3 # 2 # 1 #”
P = [0 1 0 1 0 1 0 1 0 9 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 9 0 1 0 1 0 1 0 1 0]
总结算法
Manacher算法的核心就是计算子串长度数组P。亮点是利用已知信息在计算过程中偷懒。
朴实的理解过程如下：
- 从0开始计算P[i]，并设定已知范围。
- 如果以P[i]为中心，P[i]在已知范围内的对应点的最长子串半径为半径。