Manacher回文算法 —— 镜子里的对称世界
较难4Manacher算法：用镜像魔法快速找到所有回文
小朋友，你有没有发现有些词语正着读和反着读一模一样？比如 “上海自来水来自海上” 、 “abba” ，这种字符串就叫 回文（palindrome）。在编程中，我们经常需要从一个长字符串里找出 最长的回文子串（比如“abacaba”本身就是回文，长度7）。
最简单的办法是：枚举每个位置作为中心，向两边扩展，检查左右字符是否相等。但这种方法很慢——假如字符串长度是 n，最坏情况要检查差不多 n² 次，比如 "aaaa...a" 这种全是相同字符的串。
Manacher 算法就像一位聪明的魔法师，它利用回文的 对称性，把时间复杂度降到了 O(n)。它的核心思想是：当你已经知道一个回文串时，它左右两边的字符是镜像对称的。那么右边的字符就可以用左边对称位置的信息直接“抄作业”，省去很多次比较。
1. 什么是回文的对称性？—— 照镜子的感觉
想象你站在一面镜子前，你举起左手，镜子里的你举起右手。回文也是这样的：以中心为镜面，左边和右边一模一样。
比如字符串 "abacaba"：
- 中心字符是
'a'（索引3）。 - 左半边是
"aba"，右半边是"aba"，完全对称。 - 如果我们知道中心左边的某个位置（比如索引2的
'a'）的回文半径（即以它为中心能扩展多少），那么它对称到右边（索引4的'a'）的回文半径 至少 和左边一样大，因为整个大回文保证了镜像对称。
生活中的例子：你在操场上排队做操，老师喊：“以中间同学为轴，左右对称！”那么你只要知道左边同学的动作，右边同学就能立刻做出一样的动作，不用老师再教一遍。
2. 如何统一处理奇数和偶数长度的回文？—— 插入隔板
回文有两种：
- 奇数长度：中心是一个字符，比如
"aba"（中心是 'b'）。 - 偶数长度：中心在两个字符之间，比如
"abba"（中心在 'b' 和 'b' 中间）。
为了用同一套方法处理，Manacher 算法在所有字符之间（包括开头和结尾）插入一个 特殊字符（比如 #）。这样原来的奇数长度和偶数长度都会变成奇数长度。
例如：
- 原串
"aba"→"#a#b#a#"，每个字符都被#隔开，中心是'b'（原来也是奇数）。 - 原串
"abba"→"#a#b#b#a#"，中心是中间的#（原来偶数变成以#为中心的奇数）。
插入后，新字符串的每个位置都可以作为中心，回文半径 radius[i] 表示以 i 为中心能向两边扩展多少个字符（包括中心的 # 也算在内）。回文半径减1（或者直接 radius[i]）就对应原串中的回文长度。
3. 算法核心：维护最右边界和中心
我们用一个变量 right 表示 当前所有已发现的回文串中，最靠右的右边界（即 center + radius[center]），对应的中心记为 center。
当我们从左到右扫描每个位置 i 时：
-
如果
i在右边界的左边（i < right），那么可以利用对称性：i关于center的对称位置是mirror = 2 * center - i。因为mirror的回文半径radius[mirror]我们已经算过了，而整个大回文（以center为中心）保证了mirror和i的周围字符是对称的，所以radius[i]至少等于min(radius[mirror], right - i)。- 为什么取最小值？因为如果
mirror的回文半径超过了right - i，说明mirror的部分超出了大回文的左边界，那么i的右边部分就会超出大回文的右边界，我们无法确认超出部分是否对称，只能保证在right - i范围内是安全的。
- 为什么取最小值？因为如果
-
然后继续向两边扩展：即使利用了对称性，我们还要检查
i - radius[i] - 1和i + radius[i] + 1是否相等，如果相等就增加半径。这一步保证了不会漏掉大回文之外可能存在的更长回文。 -
更新
center和right：如果i + radius[i] > right，说明我们找到了一个更靠右的右边界，就把center更新为i，right更新为i + radius[i]。 -
记录最大回文半径：
radius[i]对应的原串回文长度是radius[i]（因为插入#后，半径减1就是原串长度，但为了方便我们直接记录半径，最后返回最大值即可）。
举个例子：字符串 "babab"，插入 # 后变成 "#b#a#b#a#b#"。
- 扫描到中心
i = 3（对应原串的'a'）：此时center可能是之前的某个位置，right覆盖到了哪里？
我们可以一步一步手算，但核心是：当计算i = 5（第二个'b'）时，它的镜像位置是i = 1，而radius[1]已知，就能快速得到radius[5]的初始值。
4. 完整可运行的代码示例（带详细注释）
下面的 C++ 代码实现了 Manacher 算法，可以返回最长回文子串的长度。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int manacher(const string& s) {
// 1. 插入特殊字符 '#'，统一奇偶长度
string t = "#"; // 开头也加 #
for (char c : s) {
t += c;
t += '#'; // 每个字符后跟一个 #
}
int n = t.size(); // 新字符串长度
vector<int> radius(n, 0); // radius[i]: 以 i 为中心的回文半径（包括自己）
int center = 0, right = 0; // 当前最右回文的中心和右边界（右边界是开区间，即 i+radius[i]）
int maxLen = 0; // 记录最大回文半径
for (int i = 0; i < n; i++) {
// 2. 利用对称性初始化半径
if (i < right) {
int mirror = 2 * center - i; // i 关于 center 的对称位置
radius[i] = min(radius[mirror], right - i); // 取最小值保证不越界
}
// 3. 向两边扩展，检查是否还能增加半径
while (i - radius[i] - 1 >= 0 && i + radius[i] + 1 < n &&
t[i - radius[i] - 1] == t[i + radius[i] + 1]) {
radius[i]++;
}
// 4. 更新最右边界和中心
if (i + radius[i] > right) {
center = i;
right = i + radius[i];
}
// 5. 记录最大半径（原串中回文长度 = radius[i]）
if (radius[i] > maxLen) {
maxLen = radius[i];
}
}
return maxLen; // 最大回文子串的长度
}
int main() {
string s = "abacaba";
cout << "最长回文子串长度: " << manacher(s) << endl; // 输出 7
string s2 = "babad";
cout << "最长回文子串长度: " << manacher(s2) << endl; // 输出 3 (如 "bab" 或 "aba")
string s3 = "a";
cout << "最长回文子串长度: " << manacher(s3) << endl; // 输出 1
string s4 = "cbbd";
cout << "最长回文子串长度: " << manacher(s4) << endl; // 输出 2 ("bb")
return 0;
}
运行结果：
最长回文子串长度: 7
最长回文子串长度: 3
最长回文子串长度: 1
最长回文子串长度: 2
5. 新手容易犯的常见错误
- 忘记插入特殊字符：直接对原串使用中心扩展，会导致偶数长度回文很难处理，代码复杂化。
- 对称位置计算错误：
mirror = 2 * center - i是公式，有些同学会写成center - (i - center)，容易算错。 - 初始化半径时没有取最小值：如果直接写成
radius[i] = radius[mirror]，可能让半径超出右边界，导致后续扩展时数组越界或得到错误结果。 - 更新
right时用i + radius[i]还是i + radius[i] - 1？：我们维护的right是 开区间，即center + radius[center]是不包含的右边第一个位置，这样写if (i < right)比较方便。如果不注意，更新时可能多1或少1。 - 返回结果时混淆：
radius[i]是插入#后的回文半径，原串回文长度就是radius[i]（因为中心可能是#也可能是字符，但长度计算一致）。例如"a"插入后变成"#a#"，以'a'为中心半径为 1，返回 1 正确。
6. 相关知识点指引
- KMP 算法：也是利用“已匹配信息”避免重复比较，但用于字符串匹配。
- 字符串哈希：可以用预处理哈希值快速判断回文，但时间复杂度
O(n log n)或O(n)（配合二分），Manacher 更纯粹。 - 动态规划：可以用区间 DP 判断回文，但时间复杂度
O(n^2)，空间O(n^2)，不如 Manacher。 - 最长回文子串的变体：比如找出所有回文子串、计算回文子串个数等，Manacher 稍加改造也能完成。
Manacher 算法虽然看起来很巧妙，但只要我们理解了“镜像对称”和“最右边界”的概念，就像学会了用镜子复制信息，再长的字符串也能快速找到所有回文！尝试在自己的代码中用一用吧，下次遇到回文问题，你就是那个聪明的魔法师。
例题精讲
在Manacher算法中，向原字符串插入特殊字符（如'#）的主要目的是什么？
Manacher算法中，变量c表示当前已找到的回文子串中，最右边界的中心位置，变量r表示该回文子串的右边界。
下面是Manacher算法中计算回文半径数组d的核心代码片段，其中s是已插入特殊字符的新字符串，n是s的长度。请填写空白处的代码，使得当i当前位置没有被当前最右回文覆盖时，进行朴素的中心扩展。
int c = 0, r = 0;
vector<int> d(n);
for (int i = 0; i < n; i++) {
if (i < r) {
int j = 2 * c - i;
d[i] = min(d[j], ___);
} else {
d[i] = 1;
}
// 尝试扩展
while (i - d[i] >= 0 && i + d[i] < n && s[i - d[i]] == s[i + d[i]]) {
d[i]++;
}
// 更新c和r
if (i + d[i] > r) {
c = i;
r = i + d[i];
}
}对于一个长度为n的原始字符串，经过Manacher算法预处理（插入n+1个特殊字符）后，新字符串的长度为2n+1。以下关于Manacher算法时间复杂度的描述，正确的是哪一项？
下列代码实现Manacher算法求原始字符串s中的所有回文子串个数（包括长度为1的）。预处理后调用countPalindromes函数返回个数。请补全空缺处的代码，使得函数正确返回奇回文和偶回文的总数。
int countPalindromes(string s) {
string t = "#";
for (char ch : s) {
t += ch;
t += '#';
}
int n = t.size();
vector<int> d(n);
int c = 0, r = 0;
long long ans = 0;
for (int i = 0; i < n; i++) {
if (i < r) {
d[i] = min(d[2*c - i], r - i);
} else {
d[i] = 1;
}
while (i - d[i] >= 0 && i + d[i] < n && t[i - d[i]] == t[i + d[i]]) {
d[i]++;
}
if (i + d[i] > r) {
c = i;
r = i + d[i];
}
// 累计回文子串数量：每个中心i贡献d[i]个回文（半径为1到d[i]-1对应原始回文）
ans += ___;
}
return (int)ans;
}