高效查找最长回文子串（Python实现Manacher算法详解）

Manacher算法的核心思想

Manacher算法的关键在于利用回文的对称性来避免重复计算。它通过维护一个“回文半径数组”（通常记为 P），以及两个指针：center（当前已知最右回文的中心）和 right（当前已知最右回文的右边界）。

为了统一处理奇数长度和偶数长度的回文，算法首先对原字符串进行预处理：在每个字符之间插入特殊符号（如 #），并在首尾加上不同的边界符（如 ^ 和 $）。

Python实现步骤详解

第1步：预处理字符串

def preprocess(s):    if not s:        return "^$"    result = "^"    for char in s:        result += "#" + char    result += "#$"    return result

例如，输入 "aba" 会被转换为 "^#a#b#a#$"。这样所有回文都变成奇数长度，便于统一处理。

第2步：实现Manacher算法主逻辑

def manacher(s):    # 预处理字符串    T = preprocess(s)    n = len(T)    P = [0] * n  # 回文半径数组    center = right = 0  # 当前中心和右边界    for i in range(1, n - 1):        # 利用对称性获取初始半径        mirror = 2 * center - i        if i < right:            P[i] = min(right - i, P[mirror])        # 尝试扩展回文        try:            while T[i + (1 + P[i])] == T[i - (1 + P[i])]:                P[i] += 1        except IndexError:            pass        # 更新中心和右边界        if i + P[i] > right:            center, right = i, i + P[i]    # 找出最大回文半径及其位置    max_len = max(P)    center_index = P.index(max_len)    # 计算原始字符串中的起始位置    start = (center_index - max_len) // 2    return s[start:start + max_len]

第3步：测试代码

if __name__ == "__main__":    test_str = "abcbad"    result = manacher(test_str)    print(f"输入字符串: {test_str}")    print(f"最长回文子串: {result}")    # 输出: 最长回文子串: abcba

算法复杂度分析

• 时间复杂度：O(n) —— 每个字符最多被访问常数次。
• 空间复杂度：O(n) —— 需要额外的数组存储回文半径。

总结

通过本文，你已经掌握了如何用 Python实现Manacher算法来高效查找最长回文子串。该算法充分利用了回文的对称性质，是字符串处理中的利器。无论你是准备面试还是解决实际问题，理解并掌握这一算法都将大有裨益。

记住，关键点在于：预处理字符串、维护回文半径数组、利用对称性减少重复计算。多加练习，你也能轻松驾驭这个优雅的算法！