Manacher回文算法 - 数据结构与算法-学习笔记-上海佼艾

一、算法概述

Manacher算法（又称马拉车算法）是由计算机科学家Glenn K. Manacher于1975年提出的一种用于在给定字符串中查找所有回文子串的高效算法。该算法最著名的应用是以O(n)线性时间复杂度解决"最长回文子串"（Longest Palindromic Substring, LPS）问题，相较于暴力解法的O(n³)或中心扩展法的O(n²)，性能有了质的飞跃。

"回文"（Palindrome）是指正着读和反着读完全相同的字符串，例如"aba"、"abba"、"level"等。判断回文看似简单，但要在长度为n的字符串中高效地找出所有回文子串，则需要精妙的算法设计。Manacher算法巧妙利用回文的对称性质，通过维护已探测到的最右回文边界来避免大量重复计算，将时间复杂度压缩至线性级别，是字符串处理领域的经典算法之一。

核心优势：Manacher算法能够在O(n)时间内找到字符串的所有回文子串（包括奇回文和偶回文），而非仅找出最长的那一个。这使得它在回文子串计数、前缀回文判断等问题中同样高效。

二、回文字符串基础

在深入Manacher算法之前，需要先理解回文字符串的核心概念。

2.1 回文的定义

一个字符串S如果满足S = reverse(S)（即反转后与原字符串相等），则称S为回文字符串。例如，"racecar"反转后仍然是"racecar"，是一个回文串。

2.2 奇回文与偶回文

根据长度的奇偶性，回文分为两类：

奇回文（Odd-length Palindrome）：长度为奇数，有唯一的中心字符。例如"abcba"的中心字符为"c"，回文半径为2（从中心向两侧各扩展2个字符）。
偶回文（Even-length Palindrome）：长度为偶数，没有唯一的中心字符，对称中心在两个字符之间。例如"abba"的中心在"b"和"b"之间，回文半径为2。由于偶回文没有单一的中心字符，在处理时通常需要额外处理。

2.3 回文半径

回文半径（Palindrome Radius）是指以回文中心为起点，向左右两侧扩展的长度（包含中心本身）。对于长度为len的奇回文，其回文半径为(len+1)/2；对于长度为len的偶回文，其回文半径为len/2。例如：

字符串"abcba"——以"c"为中心，回文半径为3（覆盖"a"+"bcb"+"a"）
字符串"abba"——若将中心理解为两个"b"之间，则回文半径为2（覆盖"ab"+"ba"）

Manacher算法通过巧妙的预处理，将偶回文统一转化为奇回文处理，大幅简化了逻辑。

思考：在一个长度为n的字符串中，回文子串的总数最多可达O(n²)个（例如全为相同字符的字符串"aaaa"有10个回文子串）。因此，即使是Manacher算法也无法显式输出所有回文子串，但它能以O(n)的代价计算出每个位置的回文半径信息，进而快速回答各类回文相关问题。

三、问题分析与暴力解法

3.1 最直接的方法：暴力枚举

最直观的解法是枚举所有可能的子串，然后逐一判断是否为回文。枚举所有子串需要O(n²)的时间，判断每个子串是否为回文需要O(n)的时间，总复杂度为O(n³)。

def longest_palindrome_bruteforce(s):
    n = len(s)
    longest = ""
    for i in range(n):
        for j in range(i, n):
            sub = s[i:j+1]
            if sub == sub[::-1]:
                if len(sub) > len(longest):
                    longest = sub
    return longest

# 测试
print(longest_palindrome_bruteforce("babad"))  # 输出 "bab" 或 "aba"

3.2 中心扩展法

中心扩展法将复杂度降低到O(n²)。其思路是：每个回文都有一个中心（奇回文的中心是一个字符，偶回文的中心是两个字符之间的间隙），枚举所有可能的中心并尝试向两侧扩展。共有2n-1个可能的中心（n个字符和n-1个间隙），每次扩展最多O(n)步。

def longest_palindrome_expand(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return right - left - 1

    start, max_len = 0, 0
    for i in range(len(s)):
        len1 = expand(i, i)        # 奇回文扩展
        len2 = expand(i, i + 1)    # 偶回文扩展
        cur_len = max(len1, len2)
        if cur_len > max_len:
            max_len = cur_len
            start = i - (cur_len - 1) // 2
    return s[start:start + max_len]

中心扩展法虽然比暴力枚举高效，但当字符串长度达到10⁵甚至10⁶时，O(n²)的复杂度仍然无法接受。Manacher算法正是为了解决这一瓶颈而设计。

四、字符串预处理——统一奇偶回文

Manacher算法首先对原始字符串进行预处理，在所有字符之间（包括两端）插入一个特殊的分隔符（通常用"#"表示），目的是将偶回文转化为奇回文，从而统一处理逻辑。

预处理示例：

原始字符串："abba"（偶数长度，偶回文）

预处理后："#a#b#b#a#"（长度为9，奇数）

原始字符串："aba"（奇数长度，奇回文）

预处理后："#a#b#a#"（长度为7，奇数）

经过预处理后，新字符串T的长度为2n+1（n为原始字符串长度），且T中的所有回文子串都是奇数长度。这样一来，我们只需考虑奇回文的扩张，无需区分奇偶两种情况，大大简化了算法实现。原字符串中的回文子串与新字符串中的回文子串存在一一对应关系：以T[i]为中心的臂长p[i]对应原字符串中以某个位置为中心的回文半径。

def preprocess(s):
    """
    在原始字符串的字符之间和两端插入"#"分隔符
    例如: "abc" -> "#a#b#c#"
    """
    return "#" + "#".join(s) + "#"

# 验证预处理效果
print(preprocess("aba"))   # "#a#b#a#"
print(preprocess("abba"))  # "#a#b#b#a#"

为什么预处理能统一奇偶？原始字符串中的每个字符和每两个字符之间的间隙，在经过"#"插入后都变成了新字符串中一个单一的字符位置。偶回文的对称中心原本在两个字符之间，预处理后变成了一个"#"，因此所有回文都有了一个显式的中心位置。

五、核心思想——利用回文对称性

Manacher算法的核心在于利用回文的对称性来避免重复的中心扩展操作。这是整个算法最精妙的部分。

5.1 关键变量

算法维护以下关键变量：

p[i]：以预处理字符串T中第i个字符为中心的最大回文半径（臂长），即从i向两侧扩展p[i]步能形成回文。p[i] - 1即为原字符串中对应回文的实际长度。
center：当前已探测到的、能延伸到最右侧的回文的中心位置。
rightmost：当前已探测到的所有回文的最右边界（即center + p[center] - 1）。

5.2 核心递推关系

在遍历字符串T时，假设当前已处理到位置i，算法可以分两种情况讨论：

情况一：i < rightmost

（在已知回文范围内）

此时可以利用对称性。找到i关于center的镜像位置mirror = 2 * center - i。由于center位置的回文覆盖了从leftmost到rightmost的整个范围，且该范围是对称的，位置i处的回文半径至少为min(p[mirror], rightmost - i)。在此基础之上再尝试向两侧扩展。

情况二：i >= rightmost

（超出已知回文范围）

无法利用任何已有信息，只能从i开始向两侧暴力扩展（即臂长从0开始递增），并相应地更新center和rightmost。

5.3 直观理解

假设我们已经找到了一个以center为中心的大回文，覆盖范围从leftmost到rightmost。现在要处理位置i（在leftmost到rightmost之间）。因为整个区间是回文的，i的镜像位置mirror与i关于center对称。如果以mirror为中心有一个回文，那么以i为中心也应该有一个至少同样大的回文，但不能超出(leftmost, rightmost)的范围——因为超出范围的部分我们还没有检查过，无法保证对称性。

Manacher相对于中心扩展法的效率提升：中心扩展法对每个中心都从头开始扩展，而Manacher利用已知回文的对称性，为每个位置预估了一个初始臂长（即无需重复检查的部分），然后只在~~未知区域~~进行扩展。正是这个初始预估避免了大量重复计算。

六、算法实现

6.1 Python完整实现

以下是Manacher算法的完整Python实现，包含详细的注释说明。

def manacher(s):
    """
    Manacher算法求最长回文子串
    返回: (最长回文子串, 起始索引, 长度)
    时间复杂度: O(n), 空间复杂度: O(n)
    """
    # 步骤1: 字符串预处理
    T = "#" + "#".join(s) + "#"
    n = len(T)

    # p[i]: 以T[i]为中心的最大回文臂长
    p = [0] * n

    center = 0       # 当前最右回文的中心
    rightmost = 0   # 当前最右回文的右边界

    for i in range(n):
        # 步骤2: 利用对称性计算初始臂长
        if i < rightmost:
            mirror = 2 * center - i
            p[i] = min(rightmost - i, p[mirror])

        # 步骤3: 中心扩展（尝试扩大臂长）
        while (i - p[i] - 1 >= 0 and
               i + p[i] + 1 < n and
               T[i - p[i] - 1] == T[i + p[i] + 1]):
            p[i] += 1

        # 步骤4: 更新最右回文边界
        if i + p[i] > rightmost:
            center = i
            rightmost = i + p[i]

    # 步骤5: 找出最大臂长及其中心位置
    max_radius = max(p)
    center_idx = p.index(max_radius)

    # 步骤6: 映射回原字符串
    start = (center_idx - max_radius) // 2
    length = max_radius
    return s[start:start + length], start, length

6.2 C++实现

// Manacher算法 - C++实现
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string manacher(string s) {
    // 1. 预处理
    string T = "#";
    for (char c : s) {
        T += c;
        T += "#";
    }
    int n = T.size();
    vector<int> p(n, 0);
    int center = 0, rightmost = 0;

    for (int i = 0; i < n; ++i) {
        // 2. 利用对称性
        if (i < rightmost) {
            int mirror = 2 * center - i;
            p[i] = min(rightmost - i, p[mirror]);
        }

        // 3. 中心扩展
        while (i - p[i] - 1 >= 0 &&
               i + p[i] + 1 < n &&
               T[i - p[i] - 1] == T[i + p[i] + 1]) {
            p[i]++;
        }

        // 4. 更新最右边界
        if (i + p[i] > rightmost) {
            center = i;
            rightmost = i + p[i];
        }
    }

    // 5. 找最大臂长
    int max_r = 0, idx = 0;
    for (int i = 0; i < n; ++i) {
        if (p[i] > max_r) {
            max_r = p[i];
            idx = i;
        }
    }

    // 6. 映射回原串
    int start = (idx - max_r) / 2;
    return s.substr(start, max_r);
}

6.3 算法执行过程演示

以字符串"babad"为例，演示Manacher算法的执行流程（经过预处理后T = "#b#a#b#a#d#"）：

# 手动模拟执行过程
T = "# b # a # b # a # d #"
i = 0: p[0] = 0 ('#'), 扩展后仍为0, center=0, rightmost=0
i = 1: p[1] = 0 ('b'), 扩展后p[1]=1, center=1, rightmost=2
i = 2: p[2] = 0 ('#'), 无法扩展, arm=0
i = 3: p[3] = 0 ('a'), 扩展后p[3]=2, center=3, rightmost=5
i = 4: i<rightmost, mirror=2, p[4]=min(1,0)=0, 扩展后p[4]=2, center=4, rightmost=6
i = 5: i<rightmost, mirror=3, p[5]=min(1,2)=1, 扩展后p[5]=4, center=5, rightmost=9
i = 6: i<rightmost, mirror=4, p[6]=min(3,2)=2, 扩展无法继续
i = 7: i<rightmost, mirror=3, p[7]=min(2,2)=2, 扩展无法继续
i = 8: i<rightmost, mirror=2, p[8]=min(1,0)=0, 扩展后p[8]=1, center=8, rightmost=9
... 依次类推

# 最终p数组: [0,1,0,2,0,4,0,2,0,1,0]
# 最大p值为4 (在i=5, 对应T中的'b')
# 映射回原串: start=(5-4)//2=0, length=4
# 最长回文子串: "baba" 或 "abad"

七、时间复杂度分析

7.1 为什么是O(n)

Manacher算法的时间复杂度为O(n)，这一结论并非显而易见。直观理解如下：

关键观察：每次while循环中的中心扩展操作，都会使得rightmost增大至少1。即使某次扩展只前进了1步，rightmost也相应地增加了1。
rightmost的移动上限：rightmost的初始值为0，最终值不会超过预处理字符串T的长度2n+1。因此，整个算法过程中，中心扩展操作的总次数不会超过O(n)。
关于循环体：算法主体是一个for循环遍历T中的所有位置（共2n+1个），外部循环次数为O(n)。内部while循环的总执行次数受限于rightmost的增长，累计为O(n)。

O(n)的严格证明：在for循环的每次迭代中，要么rightmost保持不变（情况一，直接由对称性得出初始值且无法扩展），要么rightmost增加至少1（情况二或扩展成功）。rightmost单调递增且上限为2n+1，因此while的总执行次数为O(n)。加上for循环的O(n)次迭代，总时间复杂度为O(n)。

7.2 空间复杂度

Manacher算法需要存储臂长数组p，其长度等于预处理字符串T的长度2n+1，因此空间复杂度为O(n)。如果允许修改原始字符串（使用原地预处理），则空间复杂度仍为O(n)。

算法	时间复杂度	空间复杂度	能否O(n)找出全部回文
暴力枚举	O(n³)	O(1)	否
中心扩展法	O(n²)	O(1)	否（需O(n²)枚举中心）
动态规划	O(n²)	O(n²)	是
Manacher	O(n)	O(n)	是

八、Manacher算法的应用

8.1 最长回文子串

这是Manacher算法最经典的应用。求出臂长数组p的最大值max_radius，其对应的中心位置映射回原字符串即可得到最长回文子串。

def longest_palindrome(s):
    result, _, _ = manacher(s)
    return result

# 测试用例
assert longest_palindrome("babad") in ["bab", "aba"]
assert longest_palindrome("cbbd") == "bb"
assert longest_palindrome("a") == "a"
assert longest_palindrome("ac") in ["a", "c"]

8.2 回文子串计数

利用p数组可以快速统计字符串中所有回文子串的数量。对于预处理字符串T中的每个位置i，臂长为p[i]，意味着有p[i]个以i为中心的不同半径的回文子串（半径1, 2, ..., p[i]）。映射回原字符串时，每个中心贡献(p[i] + 1) // 2个回文子串。

def count_palindromes(s):
    # 先运行Manacher获取p数组
    T = "#" + "#".join(s) + "#"
    n = len(T)
    p = [0] * n
    center = rightmost = 0

    for i in range(n):
        if i < rightmost:
            mirror = 2 * center - i
            p[i] = min(rightmost - i, p[mirror])
        while (i - p[i] - 1 >= 0 and
               i + p[i] + 1 < n and
               T[i - p[i] - 1] == T[i + p[i] + 1]):
            p[i] += 1
        if i + p[i] > rightmost:
            center = i
            rightmost = i + p[i]

    # 统计回文子串总数
    count = 0
    for i in range(n):
        # T[i]可能是字符或'#'
        # 如果T[i]是字符, p[i]//2个回文
        # 如果T[i]是#, (p[i]+1)//2个回文
        count += (p[i] + 1) // 2
    return count

# 测试
print(count_palindromes("abc"))     # 3: a, b, c
print(count_palindromes("aaa"))     # 6: a, a, a, aa, aa, aaa

8.3 前缀回文判断

判断字符串的前缀是否为回文。例如，字符串"abac"的前缀"aba"是回文，但"abac"不是。利用Manacher可以高效判断：如果以某位置为中心的回文覆盖到了字符串的开头，则该前缀为回文。

8.4 字符串附加成回文的最少字符

给定一个字符串，在末尾最少添加多少个字符使其成为回文？这个问题可以转化为：找到字符串的最长回文后缀（即以最后一个字符结尾的最长回文子串），然后将剩余的前缀反转后附加到末尾。利用Manacher可以O(n)求解。

8.5 在算法竞赛和面试中的常见变体

LeetCode 5 - 最长回文子串（经典原题）
LeetCode 647 - 回文子串计数
LeetCode 214 - 最短回文串（前缀回文问题）
Codeforces 1326D2 - Prefix-Suffix Palindrome

九、算法对比分析

9.1 Manacher vs 中心扩展法

中心扩展法是最容易理解的回文求解算法，但它在每个中心位置都会进行重复扩展。对于字符串"aaaaaaaaab"，中心扩展法在靠近末尾的位置需要大量重复扩展操作，而Manacher通过对称性大幅减少了这些重复。

9.2 Manacher vs 动态规划

动态规划解法使用二维DP表dp[i][j]表示子串s[i:j]是否为回文，复杂度为O(n²)时间和O(n²)空间。虽然DP可以求出所有回文子串，但Manacher在时间上更优（O(n) vs O(n²)），空间上更优（O(n) vs O(n²)）。

# 动态规划解法（对比参考）
def longest_palindrome_dp(s):
    n = len(s)
    if n < 2:
        return s
    dp = [[False] * n for _ in range(n)]
    start, max_len = 0, 1

    # 所有单字符都是回文
    for i in range(n):
        dp[i][i] = True

    # 按子串长度递增处理
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2 or dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        max_len = length
                        start = i
    return s[start:start + max_len]

# 时间复杂度: O(n²), 空间复杂度: O(n²)

9.3 总结对比

对比维度	Manacher算法	中心扩展法	动态规划
时间复杂度	O(n) ★最佳	O(n²)	O(n²)
空间复杂度	O(n)	O(1) ★最佳	O(n²)
实现难度	中等	简单 ★	简单
求最长回文	支持	支持	支持
回文计数	O(n) ★	O(n²)	O(n²)
适用场景	大规模数据	快速原型/小规模	教学/需要DP表

选型建议：在面试或竞赛中遇到回文子串相关问题，若n ≤ 1000，中心扩展法或DP是更简单的选择（不易写错）；若n ≥ 10⁵，则必须使用Manacher算法。在生产环境中处理长文本（如DNA序列分析、自然语言处理中的回文检测等），Manacher是首选方案。

十、核心要点总结

Manacher算法核心要点：

算法性质：线性时间O(n)求解最长回文子串及所有回文子串信息，空间复杂度O(n)
预处理：插入"#"分隔符将奇回文和偶回文统一为奇回文，原始长度n → 新长度2n+1
关键变量：臂长数组p[i]、当前最右回文中心center、当前最右边界rightmost
核心优化：利用回文的对称性，通过p[i] = min(rightmost - i, p[mirror])避免大量重复扩展
臂长含义：p[i] - 1 表示以原字符串中某位置为中心的最长回文长度；p[i] 表示预处理串中的臂长
复杂度保证：rightmost单调递增，总扩展次数O(n)，线性时间得到保证
主要应用：最长回文子串（LeetCode 5）、回文子串计数（LeetCode 647）、最短回文串（LeetCode 214）
对比优势：在n ≥ 10⁵级别的大数据面前，Manacher是唯一可行的O(n)解决方案

十一、进一步思考

11.1 算法变体与扩展

Manacher的思想可以推广到更多字符串处理问题中。例如，Z算法（Z-algorithm）利用类似的对称性思想在线性时间内计算每个后缀与原始字符串的最长公共前缀。事实上，Manacher和Z算法的内部机理有异曲同工之妙，都是通过利用已计算的信息来避免重复计算，达到线性时间的目标。

11.2 关于二维回文

Manacher算法处理的是一维字符串的回文子串。在二维矩阵中寻找回文（如上下对称、左右对称的矩形区域）是更为复杂的问题，当前没有已知的O(n²)或更优的通用解法。Manacher可以用于优化某些二维回文的判定，但无法直接推广到二维。

11.3 学习建议

掌握Manacher的推荐路径：

（1）先理解中心扩展法，这是Manacher的基础；

（2）理解预处理为什么能把偶回文转为奇回文；

（3）在纸上手动模拟一个简单示例（如"ababa"），跟踪center、rightmost和p数组的变化；

（4）理解对称性优化的数学原理：p[i] = min(rightmost - i, p[mirror])；

（5）独立实现一遍Manacher并AC LeetCode 5；

（6）尝试回文计数（LeetCode 647）和最短回文串（LeetCode 214）等问题。

11.4 实践练习

建议在编写代码时，可以先实现一个简化版本（仅包含预处理和中心扩展，不包含对称性优化），验证基本功能正确后再加入对称性优化的逻辑，通过对比两者的执行速度来体会Manacher优化的威力。

# 练习：统计"回文对"前缀（Palindromic Pairs）
# 给定一个单词列表，找出所有能拼接成回文串的单词对(i, j)
# 例如 ["ab", "a"] -> (0, 1) 因为 "ab"+"a" = "aba" 是回文
# 提示：可以用Manacher作为子过程优化检查

十二、参考资料

Manacher, G. (1975). "A new linear-time 'on-line' algorithm for finding the smallest initial palindrome of a string". Journal of the ACM.
LeetCode 5 - Longest Palindromic Substring
LeetCode 647 - Palindromic Substrings
LeetCode 214 - Shortest Palindrome
Introduction to Algorithms (CLRS) - 字符串匹配章节