Manacher 算法：在线性时间内寻找最长回文子串

回文串正着读和反着读完全相同，例如 aba、abba。寻找一个字符串中的最长回文子串，最直观的做法是枚举中心并向两侧扩展，但像 aaaaaa 这样的输入会反复比较同一批字符，最坏需要 O(n²) 时间。

Manacher（通常读作“马拉车”）算法的关键不是换一种扩展方式，而是保存已经得到的回文信息，用对称位置的答案为新中心提供起点。它把重复比较压缩掉，使最长回文子串可以在线性时间内求出。

问题与三种常见思路

给定长度为 n 的字符串 s，目标是返回其中最长的连续回文子串。注意“子串”必须连续，“子序列”则可以跳过字符，两者是不同问题。

第一步：统一奇数和偶数长度

奇数长度回文的中心是字符，例如 aba 的中心是 b；偶数长度回文的中心在两个字符之间，例如 abba 的中心在两个 b 之间。若直接在原串上处理，每个中心都要分两种情况。

在每两个字符之间以及首尾插入分隔符，就能把所有回文统一成奇数长度：

原字符串abba偶数回文的中心位于两个 b 之间

加入分隔#a#b#b#a#现在中心就是一个真实位置

回文半径#a#b#b#a#从中心向一侧可跨 4 格，原串回文长度也是 4

实际代码还会在两端放入互不相同的哨兵，使扩展时不必反复判断数组是否越界。为了让输入中即使包含 #、^ 或 $ 也不会发生冲突，后面的实现不直接拼接字符，而是建立 vector<int>：

• -2：左哨兵；
• -1：字符间的分隔符；
• 0...255：原字符串中的字节；
• -3：右哨兵。

负数标记永远不会和 unsigned char 的值相同，因此扩展一定会在哨兵处停止。

第二步：定义回文半径

令 p[i] 表示变换串中以 i 为中心、向单侧能够扩展的最大格数。也就是说，区间 [i - p[i], i + p[i]] 是一个回文。

有两个很方便的映射公式：

• 最长回文在原字符串中的长度就是 bestLen，不需要再除以 2；
• 最长回文的原串起点是 (bestCenter - bestLen) / 2。

以 abba 为例，变换串中心下标为 5，半径为 4，所以原串起点是 (5 - 4) / 2 = 0，长度为 4。

第三步：维护最右回文区间

算法从左到右扫描中心，同时维护两个量：

• center：目前向右延伸最远的回文中心；
• right：该回文区间的右端点，即 center + p[center]。

这里的 right 是已经包含在回文中的位置，不是半开区间的“下一位”。只要全文保持同一约定即可。

镜像位置从哪里来

若新中心 i 位于 right 左侧，它关于 center 的镜像位置是：

mirror = 2 * center - i;

大回文关于 center 左右对称，所以 i 附近已经处于大回文内部的字符，与 mirror 附近完全对应。于是可以先令：

p[i] = std::min(right - i, p[mirror]);

为什么一定要取最小值

p[mirror] 描述镜像中心的完整回文，但镜像回文有可能越过当前大回文的左边界。越界后的字符不再受大回文对称性保证，因此能安全复制的半径最多只有 right - i。

已知区间L·mirror·center·i·right整个 [L, right] 关于 center 对称

先复制p[mirror]→p[i]只复制仍位于已知边界内的部分

再扩展right??真正比较只发生在可能创造新最右边界的位置

完整 C++17 实现

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

std::string longestPalindrome(const std::string& s) {
    // 变换为：左哨兵, 分隔符, 字符, 分隔符, ..., 右哨兵
    std::vector<int> transformed;
    transformed.reserve(s.size() * 2 + 3);
    transformed.push_back(-2);
    transformed.push_back(-1);
    for (unsigned char ch : s) {
        transformed.push_back(static_cast<int>(ch));
        transformed.push_back(-1);
    }
    transformed.push_back(-3);

    std::vector<int> radius(transformed.size(), 0);
    int center = 0;
    int right = 0;
    int bestCenter = 0;
    int bestLen = 0;

    for (int i = 1; i + 1 < static_cast<int>(transformed.size()); ++i) {
        if (i < right) {
            const int mirror = 2 * center - i;
            radius[i] = std::min(right - i, radius[mirror]);
        }

        while (transformed[i + 1 + radius[i]] ==
               transformed[i - 1 - radius[i]]) {
            ++radius[i];
        }

        if (i + radius[i] > right) {
            center = i;
            right = i + radius[i];
        }
        if (radius[i] > bestLen) {
            bestLen = radius[i];
            bestCenter = i;
        }
    }

    const int start = (bestCenter - bestLen) / 2;
    return s.substr(start, bestLen);
}

int main() {
    for (const std::string s : {"babad", "cbbd", "abba", "a", ""}) {
        std::cout << s << " -> "
                  << longestPalindrome(s) << '\n';
    }
}

对于 babad，最长答案既可以是 bab，也可以是 aba。上面的代码只在找到严格更长的回文时更新答案，因此会保留最先遇到的 bab。

为什么算法正确

不变量一：已经计算的半径是准确的

处理位置 i 前，所有更小位置的 radius 已经由实际字符比较确定。镜像初始化只复制当前大回文内部由对称性保证相等的部分，所以不会把半径估大；随后的 while 会一直扩展到第一对不同元素，因此最终半径也不会估小。

不变量二：center 对应扫描过的最右回文

若新回文的右端 i + radius[i] 没有超过 right，旧记录仍然最右；若超过，就用新中心和新右端替换。因而每轮结束后，center 和 right 始终描述已处理中心中向右延伸最远的回文。

最长答案不会遗漏

变换后，每个奇数回文和偶数回文都对应某个位置的奇数长度回文。算法准确求出每个位置的最大半径，再取其中最大值，所以一定得到原字符串的最长回文子串。

为什么是 O(n)

变换串长度是 2n + 3，外层循环显然执行 O(n) 次。看起来每一轮还有一个 while，但镜像初始化已经跳过最右边界内的已知部分：

• 成功的新比较会把回文推过旧的 right，使 right 单调右移；
• right 最多从左端移动到变换串末尾，因此所有成功扩展合计只有 O(n) 次；
• 每个中心至多再做一次导致停止的失败比较，同样是 O(n) 次。

所以总时间为 O(n)，半径数组和变换串占用 O(n) 额外空间。

常见错误

1. 混用 right 的两种定义：有人把它写成回文最右字符，有人写成右侧第一个未包含位置。两种都能实现，但 i < right、初始化半径和更新公式必须配套。
2. 忘记截断镜像半径：直接写 radius[i] = radius[mirror] 可能复制到已知大回文之外，得到没有依据的结果。
3. 使用可能与输入冲突的哨兵：若直接拼成 ^#...#$，就要明确输入字符集不包含这些符号；整数标记更稳妥。
4. 把字节当作 Unicode 字符：std::string 按字节存储 UTF-8。若要判断中文字符回文，应先解码为 Unicode 码点序列，再运行相同算法。
5. 起点公式写错：在本文变换方式下，原串起点为 (bestCenter - bestLen) / 2，返回长度就是 bestLen。

除了最长回文还能做什么

统计所有回文子串

一个中心半径为 r 时，它贡献的原串回文数量是 (r + 1) / 2。把所有中心的贡献相加，就得到回文子串总数；相同内容出现在不同位置时会分别计数。

判断前缀或后缀回文

中心 i 的回文左端为 i - radius[i]、右端为 i + radius[i]。检查端点是否碰到变换串中的首分隔符或尾分隔符，就能筛出回文前缀、回文后缀，常用于最少添加字符构造回文。

建议测试用例

最后的记忆线索

1. 插入分隔符，把奇偶回文统一起来；
2. radius[i] 记录以 i 为中心的回文半径；
3. 用 center 和 right 保存当前最右回文；
4. 区间内部先取 min(镜像半径, 到右边界的距离)；
5. 从已知半径之外继续扩展，并在必要时更新最右边界。

Manacher 的线性速度来自一个很通用的思想：把已经证明过的对称性当作可复用信息，只为未知边界付费。理解这一点，比背下几行模板更重要。