【算法】【Python】Manacher算法实现在线性时间内求解最长回文子串

def manacher(S: str) -> str:
    # 预处理字符串，插入分隔符
    T = "^#" + "#".join(S) + "#$"
    n = len(T)
    P = [0] * n  # P[i] 记录以 T[i] 为中心的回文半径
    C, R = 0, 0  # C: 当前回文中心，R: 右边界
    max_len, center_index = 0, 0

    for i in range(1, n - 1):
        # 计算当前点的初始半径
        mirror = 2 * C - i  # 对称点
        if i < R:
            P[i] = min(R - i, P[mirror])

        # 尝试扩展回文半径
        while T[i + P[i] + 1] == T[i - P[i] - 1]:
            P[i] += 1

        # 更新回文中心和右边界
        if i + P[i] > R:
            C, R = i, i + P[i]

        # 记录最长回文子串信息
        if P[i] > max_len:
            max_len, center_index = P[i], i

    # 去掉特殊字符，计算原始字符串的起点
    start = (center_index - max_len) // 2
    return S[start: start + max_len]

# 示例
S = input().strip()
print(len(manacher(S)))

Manacher算法用线性时间解决最长回文子串问题，核心在于空间换时间和对称性复用。理解其运作需要把握三个关键点：

1. 预处理：消除奇偶差异

传统中心扩展法需分别处理奇偶长度回文，Manacher通过插入分隔符（如#）将原字符串转换为纯奇数长度的新字符串。例如：

原串：a  b  b  a → 长度4（偶）
新串：#a#b#b#a# → 长度9（奇）

这种转换确保每个有效回文中心都是确切的字符位置而非间隙，统一处理逻辑。

2. 动态维护边界：避免重复计算

维护三个核心变量：

• C：当前已知最右回文的中心位置
• R：当前已知最右回文的右边界
• P[i]：以i为中心的最大回文半径（包含自身）

算法核心逻辑流程图：

遍历每个字符i时：
1. 若i在R左侧 → 利用镜像i_mirror=C*2-i获取初始半径P[i]=min(R-i, P[i_mirror])
2. 尝试向两侧扩展 → 更新P[i]
3. 若i+P[i] > R → 更新C=i，R=i+P[i]

通过镜像对称原理，将时间复杂度从O(n²)降为O(n)。这里的关键在于：当新回文触及已知边界时，才需要暴力扩展。

3. 镜像对称的数学约束

当i处于当前回文覆盖范围内（i < R）时：

• 设i关于C的镜像点为i_mirror = 2*C - i
• 若P[i_mirror]的回文区域完全包含在C的回文区域内 → P[i] = P[i_mirror]
• 若P[i_mirror]的回文区域超出C的左边界 → P[i] = R - i
• 其他情况需要暴力扩展验证

这个过程体现了动态规划思想，通过已有计算结果约束当前计算范围。

算法步骤实例演示

以字符串"ababa"为例：

预处理后：#a#b#a#b#a#
索引：0 1 2 3 4 5 6 7 8 9 10
字符：# a # b # a # b # a #

初始化C=0, R=0，遍历时：

• i=5时（字符a），此时C=3, R=7
• i_mirror=2*3-5=1，其P[1]=2
• P[5]初始值=min(7-5,2)=2
• 扩展后实际半径3 → 更新C=5, R=8

最终最大P[i]=5（索引5处），对应原字符串中心位置2，长度5（原字符串"ababa"）

时间复杂度证明

每个字符最多被访问两次：

1. 被包含在某个回文范围内 → 直接复用镜像值（O(1)）
2. 需要暴力扩展 → 扩展后右边界R单调递增，总扩展次数不超过n次
   因此整体时间复杂度为O(n)，空间复杂度O(n)（存储P数组）

关键优势总结

1. 统一处理：消除奇偶差异简化逻辑
2. 镜像复用：利用对称性避免重复计算
3. 边界推进：R的单调递增保证线性时间
4. 空间换时间：P数组存储中间状态