manacher算法通俗理解

一点一线 • 2023-01-02 • 云技术社区 • 476 阅读

manacher算法是一种求字符串最大回文半径的o(n)的算法。回文就是以一个字符为中心左右两边的字符是相等的，如aba， aa。但是对于aa来说不是很好求解，manacher算法给出了一种很巧妙的简单放在字符前后左右插入一个特殊字符，如插入#，得到 #a#a#， 最后半径一半就是原来字符的半径。

求字符串的最大回文串半径，首先想到的是暴力求解，每一个字符都的左右两边扩展，直到字符不相等为止就可以求得最大回文半径。但是这种算法的复杂度是o(n^2)

mancher提出了一种只需要o(n)的方法，方法非常巧妙。举例介绍一下的过程。

先给出几个概念，当前最大回文中心点C， 最大回文右边界R，当前回文中心i。

1 2(i') 1 3(C) 1 2(i) 1(R) 4 5

  1. 对于i 肯定有 i > C。
  2. 当i >= C + R 时，就是当前所有回文半径是从来没有遍历过的，此时使用暴力解法。
  3. 当i < C+ R时，此时回文半径的初始值为i'（i' = i - (i - c) *2 = 2c - i）的回文半径，但是i右边还存在一些未知区域，需要进行暴力探索。

以python为例的mancher算法

  • def manacher(st):

  •     dst = ""

  •     for s in st:

  •         dst = dst + "#" + s

  •     dst = dst + "#"

  • 

  •     strlen = len(dst)

  •     R = [0]*strlen

  •     mr = 0

  •     cc = 0

  •     for i in range(1, strlen):

  •         if i < mr + cc:

  •             R[i] = R[2 * cc - i]

  •         j = R[i] + 1

  •         while i+j < strlen and i - j >= 0 and dst[i + j] == dst[i - j]:

  •             R[i] = R[i] + 1

  •             j = j + 1

  • 

  •         if R[i] > mr:

  •             mr = R[i]

  •             cc = i

  •     return int(mr/2)

  • 

  • if __name__ == '__main__':

  •     ret = manacher("ddccaaccbb")

  •     print(ret)

  •     ret = manacher("112321")

  •     print(ret)

运行结果：

3

2

更多内容请关注微信公众号: IT技术漫漫谈

本站文章资源均来源自网络，除非特别声明，否则均不代表站方观点，并仅供查阅，不作为任何参考依据！
如有侵权请及时跟我们联系，本站将及时删除！
如遇版权问题，请查看 本站版权声明
THE END
分享
二维码
海报
<<上一篇
下一篇>>