问题引入
经典问题：求最长回文子串长度
给定一个长度为 的小写字母串 ，求它的最长回文子串长度，其中 。
如果采用模拟做法，枚举每个位置作为回文中心，再不断向两侧比较，最坏情况下需要 时间，无法通过本题。但是如果利用Manacher 算法，则可以将时间复杂度降低到 。利用已经求出的回文串，将一部分答案通过对称关系直接复用，就可以减少重复的计算，提高效率。
1. 统一奇偶回文串
回文中心可能是一个字符，也可能是两个字符之间的空隙。为了统一处理，在每两个字符之间以及字符串两端插入 #，再加入两个不会出现在原串中的哨兵（^和$）：
例如 abba 变为 ^#a#b#b#a#$。处理后，所有回文串的长度都是奇数，都可以用某个字符为中心向两侧扩展。^ 和 $ 是边界哨兵，可以让扩展过程不必额外判断是否越界。
接着定义 radius[i] 为：在新串中以 为中心，向一侧最多能扩展多少个字符。在上图中，以红色 # 为中心可以向一侧扩展 个字符（左侧#a#b，右侧也为b#a#），因此 radius[i] = 4，它恰好也是原串回文 abba 的长度。插入的 # 抵消了新串长度翻倍的影响，所以最终答案就是所有 radius[i] 中出现过的最大值。
2. 利用镜像位置加速
扫描新串时，维护当前右端点最靠右的回文串：
center：这个回文串的中心；r_bound：这个回文串能到达的最右位置（该位置包含在回文串内）；i：当前准备计算的位置；mirror = 2 * center - i：i关于center的对称位置。
当 i < r_bound 时，因为区间关于 center 对称，mirror 附近已经验证过的回文信息可以复用：
radius[i] = min(radius[mirror], r_bound - i);这里取较小值，是因为 radius[mirror] 对应的回文可能超出当前已知的右边界；越过 r_bound 的部分还没有比较过，不能直接确定。
得到初始半径后，继续从两端向外比较。若新的回文串超过 r_bound，就更新 center 和 r_bound。
整个过程可以概括为：先复用镜像信息 → 从已知边界继续扩展 → 必要时更新右边界。
3. 为什么是线性复杂度
每个位置都会被扫描一次。向外扩展虽然写在 while 中，但只有成功越过当前最右边界时，r_bound 才会继续右移，而它最多从左到右移动 次。因此总时间复杂度为 ，空间复杂度为 ，可以处理 长度的字符串。
代码实现
#include <bits/stdc++.h>
using namespace std;
void solved() { string s; cin >> s;
// 插入分隔符，并在两端加入不同的哨兵^和$ string s2; s2.reserve(s.size() * 2 + 3); s2.push_back('^'); for (char c : s) { s2.push_back('#'); s2.push_back(c); } s2.push_back('#'); s2.push_back('$');
vector<int> radius(s2.size(), 0); int center = 0; int r_bound = 0; int ans = 0;
for (int i = 1; i + 1 < static_cast<int>(s2.size()); ++i) { // i 在当前回文串内时，先复用其镜像位置的信息 if (i < r_bound) { int mirror = 2 * center - i; radius[i] = min(radius[mirror], r_bound - i); }
// 尝试扩展尚未确定的部分 while (s2[i - radius[i] - 1] == s2[i + radius[i] + 1]) { ++radius[i]; }
// 当前回文串的范围超过右边界，就扩展右边界和更新回文中心 if (i + radius[i] > r_bound) { center = i; r_bound = i + radius[i]; }
ans = max(ans, radius[i]); }
cout << ans << '\n';}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
solved(); return 0;}总结
总的来说，马拉车（Manacher）算法主要分成三步走：
- 插入分隔符统一奇偶性
- 利用镜像初始化半径
- 继续扩展并更新最右边界
将整个算法思路这样拆分后更容易记忆与理解，不过在具体问题情境下也需要注意做相应的调整。