一、要解决的问题
回文串指正读反读都一样的字符串，如 level、noon。经典问题：给定字符串 s（长度可达 107），求最长回文子串的长度，或统计回文子串总数。
朴素做法是中心扩展：枚举每个中心，向两边扩。但回文有奇偶两种中心（aba 中心是 b，abba 中心在两个 b 之间），要分两种情况写两遍，复杂度 O(n²) 也会超时。
Manacher 的两个天才想法：① 在字符之间插入特殊符号
#，把奇偶两种情况统一成一种；② 利用回文的对称性，右半边的答案可以从左半边"照抄"，已算过的不再重算。二、第一步：插入 # 统一奇偶
生活类比：回文就像照镜子——中心是镜面，左右两边互为镜像。偶数长度回文（如 abba）的"镜面"落在两个字符之间，奇数长度（如 aba）落在某个字符上，两种镜面处理起来很别扭。插入 # 的妙处：给每两个字符之间都造一个可以站镜面的位置，从此所有镜面都落在字符（或 #）上，统一处理。
把 s = "abba" 变成 t = "^#a#b#b#a#$"（首尾再加两个不同的哨兵防越界）。
约定：p[i] = 以 i 为中心的回文"臂长"（中心向单侧延伸的字符数，不含中心）
新串中以 i 为中心、臂长 p[i] 的回文 ↔ 原串中一个长度恰为 p[i] 的回文
新串中以 i 为中心、臂长 p[i] 的回文 ↔ 原串中一个长度恰为 p[i] 的回文
例如 abba → #a#b#b#a#，正中间的 # 处 p = 4，对应原回文 "abba" 长 4；aba → #a#b#a#，中心 b 处 p = 3，对应 "aba" 长 3。从此只需处理一种中心，且原串回文长度直接等于 p[i]，无需换算。
三、第二步：镜像复用（核心）
维护两个量：c = 当前右边界最靠右的回文中心，R = 它对应的右边界。处理位置 i（i < R）时，i 关于 c 的镜像点是 i' = 2c − i。由于 [c−(R−c), R] 整段是回文，i 和 i' 的处境"对称"，所以：
p[i] 的初始值 = min( p[i'], R − i )，然后再尝试继续向外扩展
为什么总复杂度是 O(n)？
"逐个比较向外扩展"这步看似暴力，但每次扩展成功都会让右边界 R 至少右移一格，而 R 单调不减、最多移动 n 次。所有扩展操作加起来是 O(n)，抄答案的部分是 O(1)，故总复杂度 O(n)。
四、模板代码
// t: 已处理成 ^#a#b#...#$ 形式，长度 m；p[i] 初值为 0
int c = 0, R = 0;
for (int i = 1; i < m - 1; i++) {
p[i] = (i < R) ? min(p[2 * c - i], R - i) : 0; // 镜像抄答案
while (t[i + p[i] + 1] == t[i - p[i] - 1]) p[i]++; // 继续扩展
if (i + p[i] > R) { c = i; R = i + p[i]; } // 更新最右回文
}
// 最长回文子串长度 = max(p[i])
// 回文子串总数 = Σ (p[i] + 1) / 2五、走查一遍：s = "abba"
| i | t[i] | 扩展后 p[i] | 对应原串回文（长度 = p[i]） |
|---|---|---|---|
| 2 | a | 1 | "a"，长 1 |
| 3 | # | 0 | 无（两侧 a、b 不等） |
| 4 | b | 1 | "b"，长 1 |
| 5 | #（正中） | 4 | "abba"，长 4 ✓ |
六、能干什么 & 易错点
- 最长回文子串：max(p[i])；记录中心即可还原位置（新串下标换算回原串起点：(i − p[i]) / 2）。
- 回文子串计数：每个中心贡献 (p[i]+1)/2 个，求和即可，是"回文划分计数"类 DP 的前置。
- 与其他工具组合：回文 + 哈希可 O(1) 判回文；回文自动机（PAM）适合"不同回文串"计数，注意区分。
易错：① 镜像初值是
min(p[2c−i], R−i)，漏掉 R−i 会越界抄错；② 新串首尾哨兵 ^、$ 必须互不相同且不在原串出现；③ 下标用 1-based 写 while 扩展最不容易错。七、练习
- P3805【模板】Manacher
- 进阶：回文划分计数（p 数组 + DP）、与字符串哈希结合判回文
考情提示：Manacher 在 NOI 大纲 2025 修订版中由 NOI 级下放到提高级 7 级，是 2026 年最典型的押题点，模板务必默写级熟练。