「学习笔记」Manacher

2026/8/4 10:47:04

Manacher

描述

用于求解字符串中最长回文串的算法，可在 \(O(n)\) 的时间里求出以每一个字符为中心的回文串半径 + 最大回文串长度。

还可以用于：

统计回文子串数量；
判断某些区间是否可能是回文；
求以每个位置为中心的最长回文；
处理回文覆盖、回文贡献等字符串题。

流程

考虑用一组紧凑的信息表示字符串中的回文串：\(d_1[i], \ d_2[i]\) 表示以下标为 \(i\) 的字符为中心的长度为奇数和长度为偶数的回文串个数;

显然，二者的含义也能是最长回文串半径的长度，这个数组的信息已经可以表示原串中所有子回文串的信息；

1.朴素算法

和 KMP 一样，先考虑怎么用朴素算法求解问题；

很直观，枚举每个下标作为中心点，只要可以向左右扩展，则执行；

vector<int> d1(n), d2(n);
for (int i = 0; i < n; i++) {d1[i] = 1;while (0 <= i - d1[i] && i + d1[i] < n && s[i - d1[i]] == s[i + d1[i]]) {d1[i]++;}d2[i] = 0;while (0 <= i - d2[i] - 1 && i + d2[i] < n &&s[i - d2[i] - 1] == s[i + d2[i]]) {d2[i]++;}
}

2. Manacher

观察朴素算法可以发现，奇偶长度的回文判断的处理方式不同，因此我们在每个字符中间插入一个 # ，这样我们可以统一一个过程计算奇偶长度的回文串，即都用中心扩展方式；

同时，字符串的边界也需要添上字符，用来处理边界问题：

abba → #a#b#b#a#

随后，我们定义 \(p[i]\) 为改造后的字符串中，以下标 \(i\) 为中心的最大回文半径；

\(p[i]\) 即开头所说的 \(d_1[i], \ d_2[i]\) 在改造后的统一体现。

随后我们根据一个 “信息复用” 的主体思想进行 Manacher 的过程：

1. 维护当前最右侧回文串信息

维护已找到的最靠右的子回文串的中心 \(center\) 和右边界 \(r\);

为什么？由于回文串具有对称性，后面的中心 \(j\) 可能是一个大串 \(i\) 的右半部分。那 \(j\) 附近的结构由于对称性，显然会和 \(i\) 左半部分已经确定的 \(j\) 的对称点相似，可以复用这一处的信息。

2. 下一轮枚举

我们随后枚举下一个中心下标 \(i\) , 这里我们假设前方的所有 \(p[j] \ (j \lt i)\) 均已更新过；

这里要分两种情况讨论，即根据能不能复用对称性信息来判断：

1. i >= r

说明 \(i\) 不在当前回文串的内部，没有可以复用的信息；

我们直接调用朴素算法更新 \(p[i]\) ;

2. i < r

这说明当前中心处于维护的回文串内部，我们可以复用信息来跳过重复比较；

我们用中点坐标公式计算出 \(i\) 关于 \(center\) 的对称点 \(i' = 2 * center - i\) ;

然后我们可以直接使用 \(p[i']\) 的信息初始化 \(p[i] = min(p[i'],\ r - i)\)

- 为什么要取最小值？

由于我们当前维护且确定的最大回文范围截止到 \(r\) ，假设这个串的左边界是 \(l\)，所以我们唯一确定相同的的是 \([i,r]\) 和对称过去的 \([l,i']\)，超过这一边界的结构是不能确定的；

即 \(p[i']\) 的边界可能在 \(l\) 左边，如果这样的话，我们无法保证 \(r\) 右边有相同的结构

因此我们要取最小值安全确定初始的 \(p[i]\)

3. 扩展维护信息

初始化 \(p[i]\) 后，我们不能确定这是最终的信息，所以还需要调用朴素算法尝试扩展边界；

由于右侧没有已知信息了，只能暴力的尝试拓展；

最后我们用新得到的、最终的 \(p[i]\) 更新 \(center\) 和 \(r\) 即可。

完整代码

vector<int> manacher(string s) {string t = "#";for (auto c : s) t += c, t += '#'; //改造int n = t.size();vector<int> p(n);//j:端点最右侧回文串中心for (int i = 0, j = 0; i < n; i++) {if (2 * j - i >= 0 && j + p[j] > i) p[i] = min(p[2 * j - i], j + p[j] - i);while (i - p[i] >= 0 && i + p[i] < n && t[i - p[i]] == t[i + p[i]]) {p[i]++;}if (i + p[i] > j + p[j]) j = i;}return p;
}

借鉴了哥哥的（