本文主要是介绍[算法入土之路]Manacher算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
用处:
降低大多数回文问题的时间复杂度, 提高程序效率
经典习题:
5. 最长回文子串 - 力扣（LeetCode） (leetcode-cn.com)
代码实现:
""" @File : Manacher@Author : BabyMuu@Time : 2021/12/19 18:36
"""class Manacher:'''在基础的方法上优化几个属性 i: 寻找回文长度的当前位置R: 前序获得到的回文串的右边界L: R对应回文串的左边界center : R 和 L 的中心位置i': i 相对 center 的镜像对应元素优化方法:当 i < R 的时候根据 相对center的镜像获取到对应的元素的最长回文半径 pl[i']: len如果 len > r - i: 即 i' 的回文串左边界超出了 L则 i 的回文串长度 就等于 r - i如果 i' - len == L 则需要继续向外匹配(R + 1 与 i - len -1 位置对比)与暴力解相同如如果 i - len > l:则 i 的回文长度 与 i' 相同如果 i >= R暴力解 无法加速'''def __init__(self, pri_str):self.manacher = f'#{"#".join(pri_str)}#'self.pal_arr = [0 for i in self.manacher]def maximum_palindrome_length(self):loc, len_ = self.algorithm()return self.manacher[loc - len_: loc + len_ + 1].replace('#', '')def algorithm(self):center = right = -1max_ = -1max_str = Nonefor i in range(len(self.manacher)):# 获取最小查找长度self.pal_arr[i] = min(self.pal_arr[2 * center - i], right - i) if right > i else 1'''👆 i > 右侧边界位置 则 为 1else # 2 * center - i ==> 找到 i 相对于 center 的镜像位置1 i' - len == L 俩相同2 len > r - i --> right - i3 i - len > l --> self.pl_arr[2 * center - i]'''while i + self.pal_arr[i] < len(self.manacher) and i - self.pal_arr[i] > -1:if self.manacher[i + self.pal_arr[i]] == self.manacher[i - self.pal_arr[i]]: # 向外辐射 看是否能找到更长的回文元素self.pal_arr[i] += 1 # 如果有则加 1else: # 一旦碰到不相同的元素 则说明没有使此回文串更长的回文元素了breakif i + self.pal_arr[i] > right: # 如果右边界扩充了 则更新边界信息和中心信息right = i + self.pal_arr[i]center = iif max_ < self.pal_arr[i]:max_str = i # 最长回文子串中心点max_ = self.pal_arr[i] # 最长回文子串半径return max_str, max_ - 1 # 子串中心点位置, 抛去中心点的长度测试及结果
if __name__ == '__main__':m = Manacher("papadada")print(m.manacher)print(m.algorithm()) # (11, 5)print(m.pal_arr)print(m.maximum_palindrome_length()) # adada
# # p # a # p # a # d # a # d # a #
# [1, 2, 1, 4, 1, 4, 1, 2, 1, 4, 1, 6, 1, 4, 1, 2, 1]
这篇关于[算法入土之路]Manacher算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
