manacher算法通俗理解

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

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

对于i 肯定有 i > C。
当i >= C + R 时，就是当前所有回文半径是从来没有遍历过的，此时使用暴力解法。
当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)

运行结果：

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

本站文章资源均来源自网络，除非特别声明，否则均不代表站方观点，并仅供查阅，不作为任何参考依据！
如有侵权请及时跟我们联系，本站将及时删除！
如遇版权问题，请查看本站版权声明

THE END