Manacher 算法

本博客充分学习灵神和b站博主(提供蘑菇思路，通俗易懂理解Manacher算法如何利用回文串充分利用对称信息)

b站博主
灵神讲解

• 何为Manacher算法？(又被称为马拉车算法)
  • 首先得知道求解最长回文串的中心拓展法：依次枚举回文串的中心，然后以回文串的中心向两端拓展
  • Manacher算法就是在中心拓展法的基础上，充分利用了回文串以中心对称的回文子串是对称的，通过对称，大大减少了重复计算，把求解最长回文子串的时间复杂度降低到o(n)

题外话：Manacher算法的改进思路与KMP算法、拓展KMP算法的思路类似，就是充分利用现有的信息

Manacher算法应用

• 计算以s[i]（或者s[i]和s[i+1]）为回文中心的最长回文子串的长度
• 判断任意子串是否为回文串
• 计算从s[i]开始的最长回文子串的长度
• 计算以s[i]结尾的最长回文子串的长度

代码

• 变量解释：首先得将原始的字符串拓展，p[i]表示在拓展后的字符串中，以位置i为回文中心可以向左或向右最大拓展次数(也就是以i为回文中心的回文串的最大长度)，c,r分别用于记录最长回文串的回文中心和右边界
• 可以证明：如果i在最长回文串中，那么对称的位置就是2*c-i
• 对于转换之后的字符串s[i]所对应的原始的字符串的的其实位置(i-p[i])//2,长度就是p[i]

# Manacher算法
def manacher(s):n = len(s)s = '^#' + '#'.join(s) + '#$'n = len(s)# p表示以i为中心的拓展次数，也就是回文串长度p = [0] * n# c,r 表示最长的回文串的中心和右边界c,r = 0,0for i in range(1, n-1):#  如果当前中心在最长回文串的范围内，则可以利用对称性进行拓展（K有求解出最小值）if i <= r:p[i] = min(p[2 * c - i], r - i) # 在最小值的基础上拓展  while i+p[i]+1 < n and s[i - p[i] - 1] == s[i + p[i] + 1]:p[i] += 1# 更新最长回文串的中心和右边界if i + p[i] > r:r = i + p[i]c = ireturn max(p) 

习题

5.最长回文子串

5.最长回文子串

• 思路分析：直接套Manacher算法，关键点就是计算出原始字符串的开始位置

class Solution:def longestPalindrome(self, s: str) -> str:# Manacher算法if len(s) == 1:return snews = "^#" + "#".join(s) + "#$"n = len(news)p = [0]*n c,r = 0,0maxlen,start = 0,0for i in range(1,n):if i <= r :p[i] = min(p[2*c - i],r-i)while i+p[i]+1 < n and  news[i-p[i]-1] == news[i+p[i]+1]:p[i] += 1if p[i] > maxlen:maxlen,start = p[i],(i-p[i]) // 2if i + p[i] > r:c,r = i,i+p[i]return s[start:start+maxlen]

647.回文子串

647.回文子串

• 思路分析：使用Manacher算法求解出以i为中心的回文串的长度，那么只要累加(p[i]+1)//2即可，一定注意在这里有一个限制，是以i为中心

class Solution:def countSubstrings(self, s: str) -> int:# 直接用Manacher算法news = "^#" + "#".join(s) + "#$"n = len(news)p = [0]*n c,r = 0,0ans = 0for i in range(1,n-1):if i <= r :p[i] = min(p[2*c-i],r-i)while i + p[i] < n and news[i-p[i]-1] == news[i+p[i] + 1]:p[i]+=1ans += (p[i]+1) // 2 return ans

214.最短回文串

214.最短回文串

• 思路分析：使用Manacher算法，只要找到以原始字符串第一个字符开头的最长的回文串的长度p[i]，那么补全的时候只用补全s[p[i]:]后面的元素即可

class Solution:def shortestPalindrome(self, s: str) -> str:# Manacher算法news = "^#" + "#".join(s) + "#$"n,m = len(s),len(news)p = [0] * m c,r = 0,0ans = 0for i in range(1,m):if i <= r:p[i] = min(p[2*c-i],r-i)while i + p[i] + 1  < m and news[i-p[i]-1] == news[i+p[i]+1]:p[i] += 1if i + p[i] > r:c,r = i,i+p[i]# 计算出开始位置是否是0start = (i-p[i]) // 2if start == 0:ans = max(ans,p[i])if ans == n :return s tmp = s[ans:]return tmp[::-1] + s