关于Manacher 算法中不明之处我的理解

本文主要是介绍关于Manacher 算法中不明之处我的理解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

首先贴参考代码：

#manacher算法
#时间复杂度O(n)
class Solution:def longestPalindrome(self,s):if len(s) <= 1:return s# 每个字符之间插入 #ss = '$#' + '#'.join([x for x in s]) + '#`'p = [1] * len(ss)center = 0mx = 0max_str = ''for i in range(1, len(p)-1):if i < mx:j = 2 * center - i # i 关于 center 的对称点p[i] = min(p[j],mx-i)# 尝试继续向两边扩展，更新 p[i]while ss[i - p[i] ] == ss[i + p[i] ]: # 不必判断是否溢出，因为首位均有特殊字符，肯定会退出p[i] += 1# 更新中心if i + p[i] - 1 > mx:mx = i + p[i] - 1center = i# 更新最长串if 2 * p[i]-1 > len(max_str):max_str = ss[i - p[i]+1 : i + p[i]]return max_str.replace('#', '')

之前一直对manacher算法中以下代码不理解：

# 更新中心
if i + p[i] - 1 > mx:mx = i + p[i] - 1center = i

现解释如下：
我们设立两个辅助参数，center和mx，mx是回文串能延伸到的最右端的位置，center是延伸到最右端位置的回文串的中心。

之前看这个描述不太理解，实际上这个center，mx是过去所求的回文字符串的参数，这个之前一直不理解==
因为是过去所求回文串的参数，因此center和mx是已知的。
以下代码

if i < mx:j = 2 * center - i # i 关于 center 的对称点p[i] = min(p[j],mx-i)

实际上就是利用已知的信息对未知点进行部分更新。
这个部分更新的意思是，只从p[j]来说，因为j是i关于center的对称点，因此p[j]我们是知道的，因此我们可以利用p[j]更新p[i]，虽然不能完全更新（也就是我们并不能根据过去那个回文串完全得到p[i]），起码也利用了p[j]的一些信息。
这里举个例子：

当我们的中心点位于编号5时，此时center=5，mx=center+p[5]=5+5=10
当for循环遍历到i=8的时候，此时我们可以根据之前公式得到p[8]=min(p[j],mx-i)=min(p[2*center-i],mx-i)=min(p[2],10-8)=2，我们根据这个更新以后，关于p[8]就不需要从半径为1（本身）开始遍历啦，因此利用了过去的信息进行更新。接下来再利用回文字符串本身性质进行更新即可。即以下代码：

  # 尝试继续向两边扩展，更新 p[i]while ss[i - p[i] ] == ss[i + p[i] ]: # 不必判断是否溢出，因为首位均有特殊字符，肯定会退出p[i] += 1

进行一步步迭代即可。

这篇关于关于Manacher 算法中不明之处我的理解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---