manacher算法通俗理解

原创

一点一线

修改于 2022-03-26 19:04:17

7480

修改于 2022-03-26 19:04:17

文章被收录于专栏：计算机技术

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技术漫漫谈

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

python