第 84 课 - Manacher 回文算法

学习目标

完成本课学习后，你将能够：

理解 Manacher 算法如何利用回文串的对称性，将暴力求解最长回文子串的时间复杂度从 O(n²) 优化至 O(n)。
掌握字符串预处理的方法，将奇数和偶数长度的回文串问题统一为奇数长度问题进行处理。
分析算法中 p[i] 数组（半径数组）的含义以及中心点 C 和右边界 R 的动态维护过程。
独立编写 完整、高效的 Manacher 算法代码来解决最长回文子串问题。

核心概念

1. 回文串的挑战

一个最简单的求解最长回文子串的方法是“中心扩展法”：遍历每一个字符（以及相邻字符的间隙）作为中心，向两边扩展，直到不能构成回文。这种方法的时间复杂度是 O(n²)。Manacher 算法的核心思想是：利用已计算出的回文串的对称性，避免重复计算，从而将复杂度降至线性。

2. 关键预处理：统一奇偶

回文串有两种：奇数长度（如 “aba”）和偶数长度（如 “abba”）。这使得处理起来很麻烦。Manacher 算法的第一步是进行巧妙的预处理：

在原始字符串的每个字符之间以及首尾，插入一个统一的分隔符（通常用 # 或一个原始字符串中不会出现的字符）。
例如："abba" → "#a#b#b#a#"，"aba" → "#a#b#a#"。
预处理后，所有的回文串都变成了奇数长度，并且新字符串的长度 m = 2*n + 1。

3. 核心数组与变量

p[i] 数组（半径数组）：p[i] 表示以预处理后的字符串中下标 i 的字符为中心的最长回文串的半径长度。这个半径不包含中心字符本身。
- 例如，在 s = “#a#b#a#” 中，s[3] = ‘b’ 是一个回文中心，其回文串是 "#a#b#a#"，半径为 3（对应原字符串的 “aba”）。
- 回文串在原字符串中的实际长度 = p[i]。
中心点 C：当前已知的、右边界 R 最靠右的那个回文串的中心位置。
右边界 R：当前已知的、以 C 为中心的回文串所能触及的最右端的位置（索引）。

4. 算法核心流程

遍历预处理后的字符串 s 的每个位置 i：

镜像点计算：找到 i 关于当前中心 C 的对称点 i_mirror = 2*C - i。
利用对称性初始化 p[i]：如果 i 在 R 的覆盖范围内（i < R），则 p[i] 至少可以等于 min(p[i_mirror], R - i)。这是算法高效的关键。
中心扩展：在初始化的基础上，尝试向两边扩展，增加 p[i]。
更新 C 和 R：如果以 i 为中心的回文串的右边界 i + p[i] 超过了当前的 R，则更新 C = i, R = i + p[i]。

代码示例

def longest_palindrome_manacher(s: str) -> str:
    """
    使用 Manacher 算法找到字符串中的最长回文子串。
    :param s: 输入的原始字符串
    :return: 最长回文子串
    """
    if not s:
        return ""

    # 1. 预处理：插入分隔符 ‘#’
    t = ['#']
    for char in s:
        t.append(char)
        t.append('#')
    t = ''.join(t)  # 预处理后的字符串，长度为 m = 2*n + 1

    n = len(t)
    p = [0] * n  # p[i] 表示以 t[i] 为中心的最长回文半径
    center = 0   # 当前回文中心 C
    right = 0    # 当前回文右边界 R (最右端索引)

    max_len = 0      # 记录最长回文串的长度（在原串中）
    center_index = 0 # 记录最长回文串的中心索引（在 t 中）

    for i in range(1, n - 1):  # 首尾的 ‘#’ 不需要处理
        # 2. 利用对称性初始化 p[i]
        mirror = 2 * center - i  # i 关于 center 的对称点

        if i < right:
            p[i] = min(right - i, p[mirror])  # 核心优化步骤

        # 3. 尝试中心扩展（暴力扩展）
        # 边界条件：i + p[i] + 1 < n 且 i - p[i] - 1 >= 0
        while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1

        # 4. 更新中心 C 和右边界 R
        if i + p[i] > right:
            center = i
            right = i + p[i]

        # 5. 记录全局最长回文信息
        if p[i] > max_len:
            max_len = p[i]
            center_index = i

    # 从 t 中还原原串的最长回文子串
    # 起始索引： (center_index - max_len) // 2
    # 长度： max_len
    start = (center_index - max_len) // 2
    return s[start: start + max_len]

# 测试
if __name__ == "__main__":
    test_cases = ["babad", "cbbd", "a", "ac", "aba", "abba", "abcba", "aaaa"]
    for test in test_cases:
        result = longest_palindrome_manacher(test)
        print(f"输入: ‘{test}‘ -> 最长回文子串: ‘{result}‘, 长度: {len(result)}")

输出预期：

输入: ‘babad‘ -> 最长回文子串: ‘bab‘, 长度: 3
输入: ‘cbbd‘ -> 最长回文子串: ‘bb‘, 长度: 2
输入: ‘a‘ -> 最长回文子串: ‘a‘, 长度: 1
输入: ‘ac‘ -> 最长回文子串: ‘a‘, 长度: 1
输入: ‘aba‘ -> 最长回文子串: ‘aba‘, 长度: 3
输入: ‘abba‘ -> 最长回文子串: ‘abba‘, 长度: 4
输入: ‘abcba‘ -> 最长回文子串: ‘abcba‘, 长度: 5
输入: ‘aaaa‘ -> 最长回文子串: ‘aaaa‘, 长度: 4

实践练习

练习 1：基础应用 - 返回长度

题目：给定一个字符串 s，只使用 Manacher 算法的核心思想（不要直接调用上面的函数），返回其最长回文子串的长度。要求：完成 longest_palindrome_length 函数。示例：

def longest_palindrome_length(s: str) -> int:
    # 请在此处实现你的代码
    pass

# 测试
print(longest_palindrome_length("abba")) # 预期输出: 4
print(longest_palindrome_length("a"))    # 预期输出: 1

练习 2：所有回文串

题目：给定字符串 s，找出其所有长度大于等于 2 的回文子串，并返回一个去重的列表。提示：在 Manacher 算法遍历过程中，当 p[i] > 0 时，就代表一个以 i 为中心的回文串。你需要考虑如何从预处理字符串 t 中还原出原串的子串，并进行去重。示例：

def find_all_palindromes(s: str):
    # 请在此处实现你的代码
    pass

# 测试
print(find_all_palindromes("abba")) # 预期输出: [‘abba‘, ‘bb‘] (顺序可能不同)
print(find_all_palindromes("abc"))  # 预期输出: []

练习 3：统计回文子串数量

题目：给定字符串 s，统计其所有可能的回文子串的数量（包括长度为1的）。提示：在 Manacher 算法中，以每个位置 i 为中心，它能贡献的回文子串数量就是 p[i] + 1（例如，p[i]=3 代表它包含中心点、半径为1，2，3的共4个回文串）。示例：

def count_palindromic_substrings(s: str) -> int:
    # 请在此处实现你的代码
    pass

# 测试
print(count_palindromic_substrings("aaa")) # 预期输出: 6 ("a", "a", "a", "aa", "aa", "aaa")
print(count_palindromic_substrings("ab"))  # 预期输出: 2 ("a", "b")

常见错误

预处理后的边界问题：在代码循环中，通常从索引 1 遍历到 n-2（n 是预处理后字符串长度），因为第一个和最后一个字符必然是 #，它们作为中心时半径是0，不需要处理。忘记这个边界会导致数组越界。
混淆“半径”与“长度”：在预处理后的字符串中，p[i] 是回文半径。这个回文串在原字符串中的长度就是 p[i]。初学者容易误以为原串长度是 p[i] 或者 2*p[i]。
更新 C 和 R 的条件：只有当 i + p[i] > right 时才需要更新。p[i] 是半径，所以右边界是 i + p[i]，而不是 i + p[i] + 1。
对称点计算：镜像点 mirror = 2*C - i 是一个简单的代数关系，但初学者容易记错公式。
中心扩展时的比较对象：在 while 循环中，比较的是 t[i + p[i] + 1] 和 t[i - p[i] - 1]。p[i] 是当前已知的半径，下一个需要比较的就是半径+1位置的字符。切勿写成 t[i + p[i]] 或 t[i - p[i]]。

小结

本节课我们学习了高效的 Manacher 回文算法，其核心要点如下：

问题转换：通过插入分隔符 #，将奇偶长度回文问题统一为奇数长度问题，简化了逻辑。
关键思想：利用回文串固有的对称性。对于一个已知的、右边界最远的回文中心 C，如果新考察的点 i 在其覆盖范围内，那么 i 的回文信息可以由它的镜像点 i_mirror 部分继承，避免了大量重复计算。
核心变量：p[i]（半径数组）、center（中心）、right（右边界）是算法的三驾马车，动态维护它们的正确性是关键。
算法效率：尽管代码中包含一个 while 循环，但由于 right 边界的单调递增，每个字符最多被访问两次，因此整体时间复杂度为 O(n)，空间复杂度为 O(n)。
应用价值：Manacher 算法不仅是解决最长回文子串问题的最优解，其思想（利用对称性避免重复计算）在算法设计中具有普遍意义。

通过本课的学习，你应该能够深入理解并灵活运用 Manacher 算法，为后续学习更复杂的字符串算法（如 Z 算法）打下坚实的基础。

练习编辑器

rust