Part 6.4：Manacher 回文算法

引言：寻找最美的“对称”

回文串（Palindrome），即正读和反读都一样的字符串，如 "level"、"racecar"，在字符串世界中拥有一种独特的美感。一个经典的算法问题便是：给定一个字符串，找到其中最长的回文子串。

例如，对于字符串 "babad"，最长的回文子串是 "bab"（"aba" 也是一个答案）。对于 "cbbd"，最长的回文子串是 "bb"。

解决这个问题，有几种常见的思路：

1. 暴力枚举：枚举所有可能的子串，然后判断每个子串是否是回文。时间复杂度为 O(n³)，效率极低。
2. 中心扩展法：遍历每个字符（或两个字符的间隙），以其为中心向两边扩展，直到不再是回文为止。这种方法需要分别处理奇数长度（如 aba）和偶数长度（如 abba）的回文串，虽然可以优化到 O(n²)，但处理起来稍显繁琐。
3. 动态规划：dp[i][j] 表示子串 s[i...j] 是否是回文。dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]。时间复杂度和空间复杂度都是 O(n²)。

当 n 达到 10^5 或 10^6 级别时，O(n²) 的算法都会超时。有没有一种线性时间复杂度的解法呢？

答案是肯定的，这就是 Manacher 算法（由 Glenn Manacher 在 1975 年发明）。这个算法被国内网友戏称为“马拉车”算法，它以一种极其精妙的方式，统一了奇偶回文串的处理，并利用回文串的对称性，将时间复杂度优化到了惊人的 **O(n)**。

为什么 Manacher 算法如此重要？

• 面试价值：Manacher 算法是字符串算法中的“皇冠上的明珠”，是面试中考察候选人思维严谨性和代码实现能力的顶级难题。能完整、正确地写出 Manacher，足以证明你对字符串算法的深刻理解。
• 理论价值：它展示了如何通过巧妙的预处理和信息复用，将一个看似需要 O(n²) 比较的问题，转化为线性时间的问题，是算法优化思想的典范。

本文将带你一步步拆解这个精妙的算法，让你彻底理解“马拉车”是如何在线性时间内“跑”完全程的。

背景知识：统一奇偶回文串

Manacher 算法的第一个天才之处，就是通过插入特殊字符的方式，将所有回文串（无论奇偶）都统一为奇数长度的回文串。

方法：在一个字符串的每个字符之间以及首尾都插入一个不会出现的特殊字符，例如 #。

• "aba" -> "#a#b#a#"
• "abba" -> "#a#b#b#a#"

好处：

1. 统一处理：在新字符串中，任何回文子串的长度都是奇数，其中心要么是一个原字符，要么是一个 #。
2. 半径与长度的换算：在新字符串中，以某个字符为中心的回文子串的半径 r（包含中心），其在原字符串中对应的回文子串长度就是 r-1。
   • #a#b#a# 的中心是 b，半径是 4 (#b#a#)，原串 aba 长度为 3 = 4-1。
   • #a#b#b#a# 的中心是 b 和 b 之间的 #，半径是 5 (#b#b#a#)，原串 abba 长度为 4 = 5-1。

详细算法原理

Manacher 算法的核心思想与 Z-Algorithm 类似：维护一个当前找到的、右边界最靠右的回文子串，并利用这个回文子串的对称性来加速计算后续位置的回文半径。

1. 核心数据结构：臂长数组 p

• 状态定义：p[i] 表示在新字符串 T 中，以 T[i] 为中心的最长回文子串的臂长（即半径减一）。
  • 例如，对于 T = "#a#b#a#"，以 T[3] = 'b' 为中心的最长回文子串是 "#a#b#a#"，其半径为 4，所以臂长 p[3] = 3。

我们的目标就是在线性时间内计算出整个 p 数组。max(p) 就是最长回文子串的臂长，从而可以得到其长度。

2. 算法的“直觉”：利用对称性

算法维护两个变量：

• max_right：当前所有已发现的回文子串中，右边界能到达的最远位置。
• center：与 max_right 对应的那个回文子串的中心位置。

当我们计算 p[i] 时，如果 i 在 max_right 的左边（即 i < max_right），那么我们就可以利用对称性。

图示：利用对称性

T: ... [ ... (i_mirror) ... | ... (i) ... ] ...
            ^               ^               ^
            L             center            R = max_right

• i_mirror 是 i 关于中心 center 的对称点，i_mirror = 2 * center - i。
• 我们已经计算过 p[i_mirror]，即以 i_mirror 为中心的回文臂长。
• 由于 [L, R] 这个大回文串的对称性，以 i 为中心的回文串，在一定程度上会和以 i_mirror 为中心的回文串表现出相同的性质。

3. 严谨原理：两种情况的分析

对于 i < max_right 的情况，令 i_mirror = 2 * center - i。

Case 1: p[i_mirror] < max_right - i

以 i_mirror 为中心的回文串完全被 [L, R] 这个大回文串所包含。由于对称性，以 i 为中心的回文串的臂长也必然等于 p[i_mirror]。

p[i] = p[i_mirror]

图示：Case 1

T: ... [ ... ( ... ) ... | ... ( ... ) ... ] ...
            i_mirror          center            i

i_mirror 的回文区域完全在大回文区域内部，i 的回文区域也一样。

Case 2: p[i_mirror] >= max_right - i

以 i_mirror 为中心的回文串的左边界超出了或等于 L。由于对称性，我们只能保证以 i 为中心的回文串的臂长至少是 max_right - i。它可能还会更长！

所以，我们不能直接令 p[i] = p[i_mirror]。但我们有了一个很好的起点：

1. 先令 p[i] = max_right - i。
2. 然后从 max_right + 1 的位置开始，继续向两边暴力扩展，直到遇到不匹配的字符或边界。
3. 在扩展后，max_right 必然会被更新，同时更新 center。

如果 i >= max_right，我们没有任何信息可以利用，只能从 i 开始暴力扩展，计算 p[i]，并尝试更新 max_right 和 center。

通过这种方式，max_right 指针永远只会向右移动，永不回退，从而保证了整个算法的线性时间复杂度。

步骤分解 (Step-by-step)

1. 预处理字符串：将原字符串 s 转换为新字符串 t，插入 #。
2. 初始化：创建臂长数组 p，center = 0, max_right = 0。
3. 主循环：i 从 1 到 len(t)-1。
4. 利用对称性：
   a. 如果 i < max_right，p[i] = min(p[2*center - i], max_right - i)。
   b. 否则，p[i] = 0 (从头开始扩展)。
5. 暴力扩展：以 i 为中心，p[i] 为初始臂长，向两边扩展：while t[i - 1 - p[i]] == t[i + 1 + p[i]]，p[i]++。（注意边界检查）
6. **更新 max_right**：如果 i + p[i] > max_right，则更新 max_right = i + p[i] 和 center = i。
7. 找到最大臂长：遍历 p 数组，找到最大的臂长 max_len 和其对应的中心 center_idx。
8. 计算结果：最长回文子串的长度是 max_len，其在原字符串中的起始位置可以通过 center_idx 和 max_len 计算得出。

Python 实现

def manacher(s: str) -> str:
    """使用 Manacher 算法找到最长回文子串"""
    if not s:
        return ""

    # 1. 预处理字符串
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    
    # 2. 初始化
    p = [0] * n  # 臂长数组
    center, max_right = 0, 0
    
    # 用于记录最长回文子串的中心和长度
    max_len, result_center = 0, 0

    # 3. 主循环
    for i in range(n):
        # 4. 利用对称性计算 p[i] 的初始值
        # 如果 i 在 max_right 内部，可以利用对称性
        if i < max_right:
            i_mirror = 2 * center - i
            # p[i] 至少是 p[i_mirror] 和 max_right - i 中的较小值
            p[i] = min(p[i_mirror], max_right - i)
        # 如果 i 在外部，p[i] 初始为 0

        # 5. 暴力扩展
        # 尝试以 i 为中心，p[i] 为臂长向两边扩展
        a = i + 1 + p[i]
        b = i - 1 - p[i]
        while a < n and b >= 0 and t[a] == t[b]:
            p[i] += 1
            a += 1
            b -= 1

        # 6. 更新 max_right 和 center
        if i + p[i] > max_right:
            max_right = i + p[i]
            center = i

        # 7. 更新最长回文子串的信息
        if p[i] > max_len:
            max_len = p[i]
            result_center = i

    # 8. 从结果中提取原始字符串
    start = (result_center - max_len) // 2
    end = start + max_len
    return s[start:end]

# --- 案例测试 ---
s1 = "babad"
s2 = "cbbd"
s3 = "abacdfgdcaba"

print(f"'{s1}' 的最长回文子串是: {manacher(s1)}") # bab
print(f"'{s2}' 的最长回文子串是: {manacher(s2)}") # bb
print(f"'{s3}' 的最长回文子串是: {manacher(s3)}") # aba

复杂度推导过程

• 时间复杂度: O(n)。
  • 主循环 for i 遍历 n 次。
  • 核心在于 while 循环（暴力扩展）。看似有多重循环，但和 Z-Algorithm 一样，可以通过均摊分析证明其线性。关键在于 max_right 指针，它只会单调向右移动，永不回退。while 循环中的每一次成功比较，都会使 max_right 向右移动一位。max_right 最多从 0 移动到 n-1。因此，所有 while 循环的总执行次数是 O(n) 的。
  • 总时间复杂度为 O(n) + O(n) = O(n)。
• 空间复杂度: O(n)。
  • 我们需要一个 t 数组来存储预处理后的字符串，长度约为 2n。
  • 我们需要一个 p 数组来存储臂长，长度约为 2n。
  • 总空间复杂度为 O(n)。

优势 / 劣势 / 易错点

优势

1. 线性时间：这是解决最长回文子串问题的最优时间复杂度。
2. 统一处理奇偶：通过插入特殊字符，巧妙地避免了分情况讨论。

劣势

1. 理解成本极高：算法的逻辑，特别是利用对称性的部分，非常精妙和抽象，是学习的一大难点。
2. 代码实现复杂：边界条件多，索引换算容易出错。

易错点

1. 字符串预处理：忘记在首尾添加 #。
2. 臂长与半径：混淆 p[i] 是臂长（半径-1）还是半径。
3. 索引计算：i_mirror 的计算、暴力扩展时的 a 和 b 的边界、以及最后从 result_center 和 max_len 换算回原字符串起始位置的公式，都容易出错。
4. p[i] 初始值的确定：在 i < max_right 时，p[i] 的初始值是 min(p[i_mirror], max_right - i)，而不是直接等于 p[i_mirror]，这是因为 i_mirror 的回文串可能超出了大回文串的范围。

总结

Manacher 算法是字符串处理领域一个里程碑式的算法。它将一个看似需要 O(n²) 比较的问题，通过巧妙的预处理和对“回文对称性”这一核心性质的极致利用，压缩到了线性时间。它不仅是一个高效的工具，更是一场精彩的思维体操。

本文核心要点

✅ 核心思想：维护一个右边界最远的回文串 [center, max_right]，并利用其对称性来加速计算后续位置的臂长。
✅ 预处理技巧：插入特殊字符 #，将所有回文串统一为奇数长度处理。
✅ 核心数据：臂长数组 p[i]，表示以 i 为中心的最长回文臂长。
✅ 关键转移：当 i < max_right 时，p[i] 的初始值可以由其对称点 p[i_mirror] 推导得出。
✅ 复杂度：时间 O(n)，空间 O(n)。

掌握了 Manacher，你不仅能解决最长回文子串问题，更能深刻体会到算法设计中，如何通过挖掘问题内在的结构和对称性，来实现惊人的效率提升。在下一篇文章中，我们将学习另一个强大的字符串匹配工具——字符串哈希。