Manacher算法 | 王心俊老师信息学奥赛课件

模块 01

情景导航

先用一个「照镜子」的场景让你意识到：回文问题的重复计算，可以被对称性一次性抹掉。

故事镜廊里的对称工

工匠老马负责检查一条长长的瓷砖墙，墙上每一块砖上刻着一个字符。他的工作只有一件事：找出墙上最长的一段左右对称的花纹（回文）。

他的老办法是逐块蹲下检查：站在第 1 块砖前，向左向右各看一格，字符相同就继续往外看，直到不同为止；然后挪到第 2 块砖，重复一遍……这条墙有 10⁷ 块砖，这么干他干一辈子也干不完。

直到有一次他抬头发现：墙上有一段特别长的对称花纹，把整条光线折过去，左边的每一块砖都在右边有一块「镜像砖」。

于是他改了做法：每次只用记下「当前最靠右的那段对称花纹的圆心 id 和它的右边界 mx」。检查到第 i 块砖时，先看看它有没有落在 insidе 这段花纹里 —— 如果落在里面，那就直接去找它在左半边的镜像 j，把 j 已经量好的对称半径抄过来。

这样一来，每块砖最多被「真正地向外量」一次，剩下的位置全是抄答案，整条墙只需要从头到尾走一遍。

「对称的意义，是让右边的答案等于左边的答案。」

把这个直觉写成代码，就是 Manacher 算法（俗称「马拉车」）。它把求最长回文子串从 O(n²) 降到 O(n)，是字符串里最优雅的一次「信息复用」。

💡 Manacher 到底省掉了什么

朴素的中心扩展法中，如果我们以 每一个位置 为中心都向两边扩一遍，同一段字符会被反复比较。例如 aaaaa，每个中心都要把整段扩到底，总共 O(n²) 次比较。

但请注意：如果以 id 为中心、半径为 R 的区间是回文，那么区间内任意一点 i 关于 id 的对称点 j，其「周围的字符分布」与 i 周围完全一致。 这就是「镜像」。

于是 i 的半径可以直接参考 j 的半径：如果 j 的回文完全落在 id 的回文内部，那么 i 的半径就等于 j 的半径，一次比较都不用做；只有当 j 的回文「顶到了边界」时，我们才需要从边界外继续向外尝试扩展。

一句话总结：Manacher = 中心扩展 + 镜像复用 + 只维护最右边界 mx。

①生活类比

🪞

照镜子

镜子里的左手就是外面的右手。既然知道左右完全对称，就不必再把右边的样子重新描一遍。

→ mirror: j = 2·id − i

📖

回文对联

「上海自来水来自海上」，正着读反着读一样 —— 这就是最直观的回文串。

→ 回文串定义

🧷

给珠子之间插隔片

一串奇数颗和偶数颗的珠子，中间都插上同一个隔片，就都能找到唯一的「中轴」。

→ 插入 '#' 统一奇偶

📏

只量最靠右的那把尺

不管有多少段对称花纹，只要记住最靠右的那一段的圆心和右边界，就够用了。

→ 维护 id 与 mx

②核心定义

回文串：正着读和反着读完全相同的字符串，如 aba、abba、a（单个字符也是回文）。

回文中心：奇数长度回文的中心是一个字符（如 aba 的中心是 b）；偶数长度回文的中心是「两个字符之间的空隙」（如 ab|ba）。两者不统一，是朴素做法麻烦的根源。

变换串 t：在原串 s 的首、尾以及每两个字符之间都插入一个分隔符 #。若 s 长度为 n，则 t 长度为 2n + 1（一定为奇数）。此时 t 中任意回文的长度都是奇数，中心必为某个确定的下标 i，奇偶被统一了。

回文半径 p[i]：以 t[i] 为中心、能向两边扩展出的最大半径（含中心自身）。即 t[i−p[i]+1 .. i+p[i]−1] 是回文，且再扩一格就失配。因此 p[i] ≥ 1。

原串回文长度：t 中以 i 为中心的回文对应原串中长度为 p[i] − 1 的回文子串。所以最长回文子串长度 = max(p[i]) − 1。

id 与 mx：id 是「目前所有已求出的回文中，右端点最靠右」的那个中心；mx = id + p[id] 是该回文的右边界再往右一格。口诀：mx 是「已经安全覆盖到的最远处」。

镜像 j：当 i < mx 时，i 关于 id 的对称点为 j = 2·id − i。由对称性，p[i] 与 p[j] 高度相关。

核心转移式：p[i] = min(p[j], mx − i)（当 i < mx），然后再用 while 循环尝试继续向外扩展。

回文子串个数：所有位置上的 ⌊p[i] / 2⌋ 之和，即 Σ ⌊p[i]/2⌋（只有对应原串字符的位置贡献非零）。

📌 本讲核心知识地图

板块	核心内容	大纲
朴素做法	枚举中心 + 向两边扩展，最坏 O(n²)	【7】Manacher
统一奇偶	插入 '#'，长度变成 2n+1，中心唯一	【7】Manacher
p 数组	p[i] = 以 i 为中心的最大回文半径	【7】Manacher
镜像复用	i < mx 时 j = 2·id − i，抄 p[j] 的答案	【7】Manacher
取 min	p[i] = min(p[j], mx − i)，再尝试扩展	【7】Manacher
维护最右	i + p[i] > mx 时更新 id 与 mx	【7】Manacher
复杂度	mx 单调不减，每个字符至多被扩展一次 → O(n)	【7】Manacher
答案	最长长度 max(p)−1；回文个数 Σ⌊p/2⌋	【7】Manacher
扩展	双回文串、回文分割、回文自动机 PAM	【7】字符串

③核心口诀

🔑 三步走

先插 # 统一奇偶，再求半径 p 数组；
最后扫一遍取 max(p) − 1；
从头到尾只走一趟，复杂度 O(n)。

🔑 镜像是灵魂

落在 mx 内 才有镜像：j = 2·id − i；
先抄 min(p[j], mx − i)，再往外扩；
扩大了就更新 id 和 mx：mx = i + p[i]。

🔑 边界保平安

给 t[0] 和 t[m+1] 放两个不同的哨兵（如 '&' 和 '$'），
while 循环就可以放心地不判边界；
否则一行越界，直接 RE 爆零。

模块 02

知识探究

先把朴素做法的浪费看明白，再造出 '#' 变换串与 p 数组，最后用镜像复用把复杂度压到线性。

1回文串问题与朴素做法 O(n²)

问题：给定字符串 s（长度 n），求它的最长回文子串的长度（或找出这个子串）。

朴素中心扩展：枚举每一个可能的回文中心，向两边同时扩展，直到字符不同为止，记录最大长度。每一步扩展都是 O(1) 比较，但中心的个数是 O(n)，每个中心最坏扩展 O(n)，总计 O(n²)。

对 n = 10⁷ 的题目（如洛谷 P3805），O(n²) 是 10¹⁴ 次运算，绝无可能通过。所以必须有 O(n) 的做法。

图 1：朴素中心扩展的重复劳动 —— 同一段字符被反复比较

再看一个更省的做法：二分 + 字符串哈希 —— 二分长度 L，O(n) 检查是否存在长度为 L 的回文（对每个中心用哈希 O(1) 判断两边是否相等），总复杂度 O(n log n)。已经很不错了，但 P3805 的 10⁷ 数据下仍然危险。Manacher 可以做到 严格 O(n)。

2插入 '#'：把奇偶两种回文统一成一种

奇数长度回文的中心是一个字符，偶数长度回文的中心是两字符之间的空隙。写代码时要分成两套逻辑去扩展，非常容易写错。

Manacher 的做法是：在首尾和每两个字符之间都插入同一个分隔符 '#'，把「空隙中心」也变成一个实实在在的字符位置。

变换示意：s = "aba"（奇回文）与 s = "abba"（偶回文）都被拉成奇数长度

"aba" → "#a#b#a#"（长度 3 → 7）；中心是 t[4]='b'，p[4] = 4，回文长度 = p[4]−1 = 3

偶数回文的情况：s = "abba"

"abba" → "#a#b#b#a#"（长度 4 → 9）；中心是 t[5]='#'，p[5] = 5，回文长度 = p[5]−1 = 4

💡 三个关键事实

① 变换后长度一定是 2n + 1，一定是奇数，所以每个回文的中心都落在某个整数下标上，不会再有「空隙中心」。

② 无论原串的回文是奇数长还是偶数长，在 t 中半径都恰好等于「原串回文长度 + 1」，所以 原串回文长度 = p[i] − 1。这个式子对奇偶两种情况统一成立。

③ 由于 '#' 之间从不互相比较（分隔符只与分隔符对齐，字符只与字符对齐），插入 '#' 不会产生假的回文，一一对应关系是严密的。

3p 数组的定义与手算

定义：p[i] 表示以 t[i] 为中心、能向两侧扩展出的最大半径。等价说法：t[i − p[i] + 1 .. i + p[i] − 1] 是回文，且下一对字符 t[i − p[i]] 与 t[i + p[i]] 不相等。注意 p[i] 至少为 1（只含中心自己）。

以 s = "abacaba" 为例，变换后 t = "#a#b#a#c#a#b#a#"（长度 15）。手算 p 数组如下：

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
t[i]	#	a	#	b	#	a	#	c	#	a	#	b	#	a	#
p[i]	1	2	1	4	1	2	1	8	1	2	1	4	1	2	1

读表要点：

最大半径

p[8] = 8 最大，说明以 t[8]='c' 为中心能扩到整个 t，对应原串 "abacaba" 本身就是回文，长度 = 8 − 1 = 7。

奇回文在哪

p[4] = 4（t[4]='b'）→ 长度 3，对应原串 "aba"（s[1..3]）；p[12] = 4 → 对应 "aba"（s[5..7]）。

偶回文在哪

t 中所有 '#' 位置处的 p 值都是 1，说明 "abacaba" 里没有偶数长度的回文。若有，它一定出现在某个 '#' 位置上且 p ≥ 2。

回文总数

Σ⌊p[i]/2⌋ = 1+2+1+4+1+2+1 = 12 个回文子串（7 个单字符 + 3 个 "aba" + 1 个 "bacab" + 1 个 "abacaba"）。

4核心原理：镜像是怎么省时间的本讲重点

想象我们已经算出了一段很靠右的回文：以 id 为中心、右边界延伸到 mx = id + p[id]（注意 mx 是「再往右一格」，即回文覆盖区间为 [id − p[id] + 1, mx − 1]）。

现在要处理下标 i < mx（i 落在这段回文内部）。取 i 关于 id 的对称点 j = 2·id − i。由于整段回文关于 id 完全对称，i 周围的字符环境与 j 周围的字符环境是一模一样的。因此：

图 2：id / mx / i / j 的几何关系 —— 半径 p[j] 被镜像到 i 上

但有一个限制：我们能确信的只有「mx 以内」的部分。因为在 mx 之外没有任何已知信息，那里是否还能继续配对上，只能亲自去试。于是得到核心式子：

核心转移式

若 i < mx：p[i] = min( p[2·id − i] , mx − i )，然后再用 while 尝试继续向外扩展

若 i ≥ mx：一点信息都没有，只能从 p[i] = 1 开始老老实实向外扩

💡 为什么是 min

p[j] 是「j 能扩到的最大半径」，mx − i 是「从 i 到已知边界 mx 的距离」。两者取较小值。

直觉：i 的半径不可能超过 j 的半径（对称性给出的上界），也不可能超过 mx − i（信息量给出的上界）。 取 min 就是拿两个上界里更紧的那个。

如果 p[j] < mx − i，说明 j 的回文完全被包在已知区间内部，i 也一样，两边都不会碰到未知区域，p[i] 就直接等于 p[j]，一次字符比较都不用做。反之，如果 p[j] 顶到了边界，剩下的就只能靠 while 循环亲自往外试。

5两种情况：什么时候能「白拿」，什么时候要「亲自扩」

图 3：两种情况的对比 —— A 完全白拿，B 只白拿一部分

✅ 情况 A：p[j] < mx − i

镜像 j 的回文完全落在已知区间内（j 左右都没顶到边界）。由对称性，i 的回文也完全落在内部，p[i] = p[j]。此时 while 循环会在第一对字符上立刻失配而退出，真的做到 0 次有效比较。

⚠️ 情况 B：p[j] ≥ mx − i

镜像 j 的回文已经顶到（甚至越过）了已知区间的边界，说明对称性只能保证 i 的半径至少是 mx − i。此时 p[i] 先设为 mx − i，然后用 while 循环真正地向两边比较 —— 有可能发现 i 的回文比 mx 还长！

别忘了最后一步：while 扩完之后，如果 i + p[i] > mx，说明我们发现了更靠右的回文，必须立刻 更新 id = i、mx = i + p[i]。否则镜像条件失效，算法会退化成 O(n²)。「只维护最右那个」是线性复杂度的全部秘密。

6为什么是 O(n)：一个漂亮的摊还分析

外层 for 循环显然只跑 n 次（n 是变换串长度）。关键是 while 循环一共执行了多少次 —— 它看起来可能很多，但总数被严格限制住了。

mx 只增不减

每次更新都发生在 i + p[i] > mx 时，更新后 mx 变大。mx 是单调不减的，且始终 ≤ n + 1。

每次成功比较都推 mx 前进

while 里每成功比较一次，p[i] 加 1，于是 i + p[i] 加 1。如果当前回文的右端成了新纪录，mx 就跟着加 1；如果没成新纪录，说明 i + p[i] ≤ mx，此刻扩展马上会停（因为越界的一侧无法被对称性覆盖）。

记账结论

把「成功扩展次数」全部记在 mx 的账上：mx 从 0 涨到最多 n + 1，所以成功扩展总次数 ≤ n；而每次扩展失败只多花 O(1)。于是 while 的总代价是 O(n)。

总复杂度

O(n) 外层 + O(n) 扩展 = O(n) 时间，O(n) 空间（p、t 数组）。这个「mx 单调」的记账法，和 KMP 里「j 至多增加 n 次」是同一套思路。

做法	核心思想	时间复杂度	能否过 10⁷
暴力枚举	枚举所有子串再判回文	O(n³)	❌
中心扩展	枚举中心向两边扩	O(n²)	❌
二分 + 哈希	二分长度，哈希 O(1) 判等	O(n log n)	⚠️ 勉强
Manacher	镜像复用 + 维护最右边界	O(n)	✅
回文自动机	把回文建成一棵树（PAM）	O(n)	✅（可求本质不同回文数）

🎬分步演示：对 "abacaba" 逐个算出 p[i]

🔁 Manacher 全程：s = "abacaba" → t = "#a#b#a#c#a#b#a#"（长度 15）

0初始化：t 首尾及每两字符间插入 '#'，得到 # a # b # a # c # a # b # a #；t[0]='&'、t[16]='$' 作哨兵。id = 0, mx = 0，p 数组待填。

1i = 1：i ≥ mx（1 ≥ 0），只能从 p[1] = 1 开始。t[0]='&' 与 t[2]='a' 不等 → p[1] = 1。此时 i + p[1] = 2 > 0，更新 id = 1, mx = 2。

2i = 2：i ≥ mx（2 ≥ 2），无镜像可用。从 p = 1 向外扩：t[1]='#' 与 t[3]='#' 相等 → p = 2；再比 t[0] 与 t[4]，越界侧是哨兵 → 停。故 p[2] = 2（对应原串 "a"）。i + p = 4 > 2 → id = 2, mx = 4。

3i = 3：i < mx（3 < 4）。镜像 j = 2·2 − 3 = 1，p[j] = 1，mx − i = 1 → p[3] = min(1,1) = 1。扩展：t[2]='a' 与 t[4]='b' 不等 → 保持 1。i + p = 4 不大于 mx，不更新。

4i = 4：i ≥ mx（4 ≥ 4）。从 p = 1 扩：t[3]=t[5]='#' ✓ → 2；t[2]=t[6]='a' ✓ → 3；t[1]=t[7]='#' ✓ → 4；t[0]='&' vs t[8]='c' ✗ → 停。p[4] = 4（对应原串 "aba"）。i + p = 8 > 4 → id = 4, mx = 8。

5i = 5：i < 8。j = 2·4 − 5 = 3，p[3] = 1，mx − i = 3 → p[5] = 1。扩展 t[4]='b' vs t[6]='a' ✗ → p[5] = 1。

6i = 6：i < 8。j = 2·4 − 6 = 2，p[2] = 2，mx − i = 2 → p[6] = 2。注意这里 p[j] = mx − i，属于情况 B，要尝试扩展：t[4]='b' vs t[8]='c' ✗ → p[6] = 2。

7i = 7：i < 8。j = 8 − 7 = 1，p[1] = 1，mx − i = 1 → p[7] = 1。扩展 t[6]='a' vs t[8]='c' ✗ → p[7] = 1。

8i = 8：i ≥ mx（8 ≥ 8），无镜像。一路向外扩：t[7]=t[9]='#'、t[6]=t[10]='a'、t[5]=t[11]='#'、t[4]=t[12]='b'、t[3]=t[13]='#'、t[2]=t[14]='a'、t[1]=t[15]='#'，全部相等 → p[8] = 8，整个 t 都是回文。i + p = 16 > 8 → id = 8, mx = 16。

9i = 9：i < 16。j = 2·8 − 9 = 7，p[7] = 1，mx − i = 7 → p[9] = 1。扩展 t[8]='c' vs t[10]='a' ✗ → p[9] = 1。

10i = 10：j = 16 − 10 = 6，p[6] = 2，mx − i = 6 → p[10] = 2。扩展 t[8]='c' vs t[12]='b' ✗ → p[10] = 2。

11i = 11：j = 5，p[5] = 1 → p[11] = 1。扩展失败。

12i = 12：j = 16 − 12 = 4，p[4] = 4，mx − i = 4 → p[12] = min(4,4) = 4。这就是「照镜子」最漂亮的一步：一次字符比较都没做，就拿到了半径 4（对应原串位置 5..7 的 "aba"）。尝试再扩：t[8]='c' 与 t[16]='$' 不等 → 保持 4。

13i = 13, 14, 15：依次得 p[13] = 1、p[14] = 2、p[15] = 1。扫描结束。

14汇总：p = [_,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1]。最长回文长度 = max(p) − 1 = 7（就是 "abacaba" 本身）；回文子串总数 = Σ⌊p[i]/2⌋ = 1+2+1+4+1+2+1 = 12。

观察第 12 步：i = 12 与 j = 4 关于 id = 8 对称，而 mx − i = 4 恰好够用，所以 p[12] 直接被 p[4] 填满。这就是 Manacher 快的原因 —— 整个算法里真正「向外比较」的位置只有少数几个，其余全是抄答案。

案例1洛谷 P3805【模板】Manacher —— 完整实现

题目：给定一个只含小写字母的字符串 s（|s| ≤ 1.1 × 10⁷），求 s 的最长回文子串长度。

思路：插入 '#' 得到 t，首尾放不同哨兵，按「镜像 + 取 min + 尝试扩展 + 更新最右」跑一遍即可。

C++Manacher 模板（哨兵版，无需显式边界判断）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 11000005;      // 原串最大长度 1.1e7
char s[MAXN];                        // 原串（从下标 1 开始存）
char t[MAXN * 2 + 10];               // 变换串，长度 2n+1 再加哨兵
int  p[MAXN * 2 + 10];               // p[i]：以 t[i] 为中心的最大回文半径

int main() {
    scanf("%s", s + 1);                // ★ 字符串从 1 开始，所有下标统一
    int n = strlen(s + 1), m = 0;

    t[++m] = '#';                       // 首部插一个 '#'
    for (int i = 1; i <= n; i++) {
        t[++m] = s[i];                  // 原字符
        t[++m] = '#';                   // 每个字符后面都补一个 '#'
    }
    t[0] = '&';                       // ★ 左哨兵
    t[m + 1] = '$';                   // ★ 右哨兵（与左哨兵不同！）

    int id = 0, mx = 0, ans = 0;      // mx = id + p[id]，是「右边界再右一格」
    for (int i = 1; i <= m; i++) {
        if (i < mx)                     // ★ 有镜像可用
            p[i] = min(p[2 * id - i], mx - i);
        else
            p[i] = 1;                    // ★ 没有信息，从中心自己开始

        while (t[i - p[i]] == t[i + p[i]]) p[i]++;   // ★ 哨兵保证一定会停

        if (i + p[i] > mx) {              // ★ 发现更靠右的回文
            mx = i + p[i];              // 更新右边界
            id = i;                     // 更新中心
        }
        ans = max(ans, p[i] - 1);        // ★ 原串回文长度 = 半径 − 1
    }

    printf("%d\n", ans);
    return 0;
}

运行结果

输入: aaa
输出: 3

输入: abacaba
输出: 7

输入: abcdefg
输出: 1

（对 "aaa"：t = "#a#a#a#"，p = [_,1,2,3,4,3,2,1]，max(p) = 4 → 4 − 1 = 3 ✓）

💡 逐段解析

① 哨兵法：t[0] = '&'、t[m+1] = '$'。while 循环里 i − p[i] 最小会取到 0，i + p[i] 最大会取到 m+1。由于哨兵与任何真实字符都不相等，而且两个哨兵彼此也不相等，所以循环一定会停下来，不必写 i - p[i] >= 1 && i + p[i] <= m 这样的边界判断，既快又不容易写错。

② mx 的含义：注意 mx = id + p[id] 是右边界再加一格（而不是右边界本身）。这样写的好处是：mx − i 直接就是「i 到已知边界的距离」，不需要再 ±1；而「i < mx」正好表示「i 还在已知回文内部」。

③ 两个分支必须都写：if (i < mx) 分支用镜像初始化；else 分支把 p[i] 置 1。漏掉 else 是经典错误 —— 若上一轮遗留下来的 p[i] 值未清零，while 会从一个过大的值开始比较，直接算错。

④ 更新时机：必须在 while 之后判断 i + p[i] > mx。写成 >= 也能过，但用 > 能保证只有在真正变远时才更新，减少无意义的赋值。

⑤ 数组大小：原串最多 1.1 × 10⁷，t 和 p 都要按 2n+10 开。int p[2.2e7] 约占 88 MB，char t[2.2e7] 约占 22 MB，合计 110 MB，正好在 P3805 的 125 MB 限制内。

案例2从 t 的下标还原出原串中的那个回文子串

题目：求出最长回文子串的长度显然不够，现在要求输出这个子串本身（若长度相同取最靠左的）。

难点：t 中插了很多 '#'，怎么把「t 中的回文区间」翻译回「原串中的下标区间」？

下标映射关系：t[2j] = s[j]，t[2j+1] = '#'

设最长回文在 t 中的区间为 [L, R]，其中 L = i − p[i] + 1，R = i + p[i] − 1

原串左端点 st = (L + 1) / 2（整除），长度 len = p[i] − 1

验证：s = "abacaba"，i = 8、p[8] = 8 → L = 1，st = (1+1)/2 = 1，len = 7 → s[1..7] = "abacaba" ✓

其实还有一个更省事的等价写法：st = (i − p[i] + 2) / 2。两种写法数学上完全相同。

C++输出最长回文子串（含下标还原）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    int bestP = 0, bestI = 0;          // 记录「最大半径」与其中心
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }

        if (p[i] > bestP) {               // 严格大于 ⇒ 长度相同时保留更靠左的
            bestP = p[i];
            bestI = i;
        }
    }

    int len = bestP - 1;                  // 原串回文长度
    int L   = bestI - bestP + 1;          // t 中回文左端点
    int st  = (L + 1) / 2;                // ★ 映射回原串下标

    printf("%d\n", len);
    for (int i = st; i < st + len; i++) putchar(s[i]);
    putchar('\n');
    return 0;
}

运行结果

输入: abacaba
输出: 7
      abacaba

输入: abcdcba
输出: 7
      abcdcba

输入: aabbaa
输出: 6
      aabbaa

（"aabbaa" 的全串即回文；变换后 t = "#a#a#b#b#a#a#"，中心落在 t 中间的 '#' 上，
  p[7] = 7，L = 7 − 7 + 1 = 1，st = (1+1)/2 = 1，len = 6 → s[1..6] = "aabbaa" ✓）

💡 为什么 st = (L+1)/2 就一定对

t 的下标与 s 的下标有这样的对应：偶数下标 2j 对应 s[j]，奇数下标 2j+1 对应分隔符 '#'。

回文的左端点 L 有两种可能：

L 为偶数（L = 2j）：此时 t[L] = s[j]，原串起点正是 j = (2j + 1)/2 = (L+1)/2（整除）✓

L 为奇数（L = 2j+1）：t[L] = '#'，它夹在 s[j] 与 s[j+1] 之间，所以回文实际上从 s[j+1] 开始，而 (2j+1+1)/2 = j+1 ✓

两种情况的公式都是 (L+1)/2（整数除法），非常统一。同理可得右端点 en = (R+1)/2 对应 s 中最后一个字符的下标。

注意：长度相同时要求输出最靠左的，所以判断写成 p[i] > bestP（严格大于），这样后面的同长度解不会覆盖前面的，天然保留了最靠左的那个。

案例3统计回文子串的个数：Σ⌊p[i]/2⌋

题目：给定字符串 s，统计它共有多少个回文子串（不同位置算不同，即「回文子串出现次数」）。

结论：答案 = Σ ⌊p[i] / 2⌋（对所有 i 求和，只有对应原串字符的位置贡献非零）。

理解方式一：按中心分类

每个回文子串都有唯一的中心。在变换串里，中心落在「字符位置」上时对应奇数长度的回文（长度 1、3、5…），落在「'#' 位置」上时对应偶数长度的回文（长度 2、4、6…）。

中心 i 贡献的回文个数恰好是 ⌊p[i]/2⌋：例如 p[8] = 8 → ⌊8/2⌋ = 4，代表以该点为中心、长度分别为 1、3、5、7 的 4 个回文。

理解方式二：以 "aaa" 验证

s = "aaa"，回文子串有：a×3、aa×2、aaa×1，共 6 个。

t = "#a#a#a#"，p = [_,1,2,3,4,3,2,1]，⌊p/2⌋ = 0,1,1,2,1,1,0，求和 = 6 ✓

再看 "abacaba"：⌊p/2⌋ 求和 = 1+2+1+4+1+2+1 = 12；手工数一遍（7 个单字符 + 3 个 "aba" + 1 个 "bacab" + 1 个 "abacaba"）也是 12 ✓

C++统计回文子串个数（Manacher + 计数）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    long long cnt = 0;                  // ★ 个数可能很大，开 long long
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        cnt += p[i] / 2;               // ★ 核心公式：⌊p[i]/2⌋
    }
    printf("%lld\n", cnt);
    return 0;
}

运行结果

输入: abacaba
输出: 12

输入: aaa
输出: 6

输入: abcdefg
输出: 7

（"abcdefg" 每个字符自己都是一个回文，共 7 个；
  "aaa" → 3 + 2 + 1 = 6；
  "abacaba" → 7(单) + 3("aba") + 1("bacab") + 1("abacaba") = 12）

💡 为什么 ⌊p[i]/2⌋ 而不是 p[i] − 1？

很多人第一反应是「以 i 为中心能扩出 p[i] − 1 种长度的回文，所以贡献 p[i] − 1」。但那是把「同长度不同中心」算重了的直觉 —— 实际上变长了就换了中心。

查看详细推导

关键观察：t 中所有以 i 为中心的回文的半径是 1, 2, 3, …, p[i]，一共 p[i] 个。但半径每增加 2，对应的原串回文长度才增加 2（半径 r 对应原串长度 r − 1，奇偶由 i 的奇偶决定）。

更直白的算法：半径 1 对应的原串长度为 0（空串，不算）；半径 3 → 长度 2；半径 5 → 长度 4 …… 只有一半的半径取值能对应到非空的、奇偶正确的位置，正好是 ⌊p[i]/2⌋ 个。

换个说法：每一对「半径 +2」才新增一个真正的回文子串。所以从 p[i] 里数出 ⌊p[i]/2⌋ 个，这正好也是「以 i 为中心的回文个数」。用 "aaa" 和 "abacaba" 两个例子都验证通过。

考场技巧：不确定公式时，用 p 数组手算一个短串（如 "aaa"、"aba"、"abba"）对齐答案，比背公式可靠得多。

🚀扩展：回文自动机（PAM）与字符串哈希对照

Manacher 解决的是一维回文问题：最长回文、回文计数、以某点为中心的回文范围。但有些问题 Manacher 处理不了，例如「本质不同的回文子串有多少个」——这需要把回文建成一棵树，也就是回文自动机（Palindromic Automaton，PAM，又叫 Eertree）。

问题	Manacher 能做吗	推荐工具
最长回文子串长度	✅ O(n)	Manacher
回文子串的个数	✅ O(n)，Σ⌊p/2⌋	Manacher
输出具体的最长回文子串	✅ O(n)，下标还原	Manacher
以每个位置为结尾的最长回文	✅ 由 p 数组推出	Manacher
本质不同的回文子串个数	❌ 需去重	PAM / 哈希 + set
每个回文子串的出现次数	❌	PAM（fail 树上累加 siz）
两个串的最长公共回文	⚠️ 麻烦	PAM / Manacher + 哈希

与哈希的关系：正反两次哈希可以在 O(1) 内判断任意子串是否回文，配合二分长度得到 O(n log n) 求最长回文。哈希的优点是「一眼就会写」，缺点是常数大、容易出错、有被卡的风险。在 CSP-S 考场上，Manacher 的模板只有 20 行左右，性价比远高于「二分 + 双哈希」。

与 KMP 的思想渊源：Manacher 的「维护最右边界 mx + 镜像复用」和 Z 函数的「维护最右匹配区间 + 镜像复用」是同一个套路；而 KMP 的「失配指针跳转」与 PAM 的 fail 指针也同源。这三者合起来，就是字符串算法里「用已知信息避免重复计算」的三张面孔。

模块 03

实践应用

完整题目 + 样例 + 多角度分析 + 代码 + 运行结果。

题1最长回文子串长度

B字符串 / Manacher洛谷 P3805

题目描述

给出一个只由小写英文字母组成的字符串 s，求 s 中最长回文子串的长度。

输入格式：一行一个字符串 s。

输出格式：一行一个整数，表示最长回文子串的长度。

数据范围：|s| ≤ 1.1 × 10⁷。1s / 125MB。

输入样例：aaa 输出样例：3

🔍 方法对比

方法一 · 中心扩展枚举中心向两边扩，O(n²)。n = 10⁷ 时需要 10¹⁴ 次比较，必然 TLE。

方法二 · 区间 DP f[l][r] 表示 s[l..r] 是否回文，O(n²) 时间 + O(n²) 空间。n = 10⁷ 时空间要 10¹⁴ 字节，连数组都开不出来。

方法三 · 二分 + 字符串哈希二分答案长度 L，用哈希 O(1) 判断两边是否相等，O(n log n)。n = 10⁷ 时约 2.4 × 10⁸ 次运算，卡常严重、风险高。

方法四 · Manacher O(n)，只扫一遍，每个字符最多被扩一次。是本题唯一稳妥的解法。

核心提醒：本题 n 极大，必须用 char 数组存串、scanf("%s") 读入，且 t、p 两个数组要按 2n 开，总内存约 110 MB。

C++P3805 — 完整可提交代码（Manacher 模板）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 11000005;
char s[MAXN], t[MAXN * 2 + 10];
int  p[MAXN * 2 + 10];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;

    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';     // 两个不同的哨兵

    int id = 0, mx = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        ans = max(ans, p[i] - 1);
    }
    printf("%d\n", ans);
    return 0;
}

运行结果

输入: aaa
输出: 3

输入: abacaba
输出: 7

输入: zzzzzzzzzzzz          （12 个 z）
输出: 12

输入: abcd
输出: 1

说明：p 数组的最大值出现在全串中心处；
      "aaa"    → max p = 4 → 4−1 = 3
      "abacaba"→ max p = 8 → 8−1 = 7
      "abcd"   → max p = 2 → 2−1 = 1（任意单字符）

💡 p 数组的「奇数性」

注意在上述所有输出中，max(p) 都是偶数，答案都是奇数。这不是巧合。

查看原因

t 中下标为偶数的位置放的是原串字符，下标为奇数的位置放的是 '#'。一个以字符位置为中心的 t 回文，半径必然使得它「首尾都是 '#'」→ 半径是偶数；以 '#' 为中心的回文半径是奇数。

偶半径 ↔ 奇数长度的原串回文；奇半径 ↔ 偶数长度的原串回文。上例中所有答案都是奇数，说明这些串的最长回文都是奇数长度。

调试技巧：如果程序输出的答案与手算差 1，八成是「半径 ↔ 长度」换算写错（忘了 −1）。把 p 数组打出来，找到最大值，然后相减，比盯着最长串瞎猜快得多。

题2输出最长的那个回文子串

B字符串 / 下标还原Manacher 应用

题目描述

给定字符串 s，输出它的最长回文子串。若存在多个，输出最靠左的那个。

输入格式：一行一个字符串 s（|s| ≤ 2 × 10⁶）。

输出格式：两行，第一行最长回文子串的长度，第二行该子串本身。

输入样例：abacaba 输出样例：7
abacaba

🔍 两种还原下标的思路

思路A · 公式法（推荐）在 t 中记下最优中心 bestI 与半径 bestP，左端点 L = bestI − bestP + 1，则原串起点 st = (L + 1) / 2，长度 len = bestP − 1。O(1) 换算，最省事。

思路B · 直接在原串上重扩一遍找到最优中心对应的原串中心，再老老实实向两边扩一次。思路直观但要注意奇偶两套写法，容易写错。

结论：用思路 A。公式的推导见下面「为什么一定对」。

C++输出最长回文子串（含下标还原）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2000005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    int bestP = 0, bestI = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        if (p[i] > bestP) { bestP = p[i]; bestI = i; }   // 严格 > ⇒ 保留最靠左
    }

    int len = bestP - 1;
    int st  = (bestI - bestP + 2) / 2;          // = (L + 1) / 2
    printf("%d\n", len);
    for (int i = st; i < st + len; i++) putchar(s[i]);
    putchar('\n');
    return 0;
}

运行结果

输入: abacaba
输出: 7
      abacaba

输入: aabbaa
输出: 6
      aabbaa

输入: aabbccddee
输出: 2
      aa

输入: xabay
输出: 3
      aba

说明：末例中 "aba" 与 "bab" 同为长度 3，输出的是更靠左的 "aba"，
      说明 bestP 的比较用了严格大于。

💡 为什么 st = (L + 1) / 2 一定对

查看完整推导

t 与 s 的下标对应关系是：t[2j] = s[j]，t[2j+1] = '#'。

设最长回文在 t 中的左端点为 L = bestI − bestP + 1。

若 L 为偶数（L = 2j）：t[L] 就是 s[j]，原串起点是 j，而 (2j + 1) / 2 = j ✓

若 L 为奇数（L = 2j+1）：t[L] = '#'，它夹在 s[j] 与 s[j+1] 之间，回文实际从 s[j+1] 开始，而 (2j + 1 + 1) / 2 = j + 1 ✓

两种情况都归结为同一个公式 (L + 1) / 2（整除）。同理，右端点的映射是 en = R / 2，可以自己验算一遍。

题3统计回文子串的个数

B字符串 / 计数Manacher 应用

题目描述

给定字符串 s，统计它一共有多少个回文子串（相同内容但位置不同算不同的子串）。

输入格式：一行一个字符串 s（|s| ≤ 5 × 10⁶，保证答案不超过 2⁶³−1）。

输出格式：一行一个整数，表示回文子串个数。

输入样例：abacaba 输出样例：12

🔍 方法对比

方法一 · 枚举所有子串判回文 O(n³)，n = 5 × 10⁶ 时完全不可行。

方法二 · 每对 (l, r) 用哈希判回文 O(n²) 枚举，n² = 2.5 × 10¹³，仍然 TLE。

方法三 · Manacher + 公式结论是 Σ ⌊p[i] / 2⌋，扫一遍 p 数组即得 O(n)。

注意：答案可能很大（n = 5 × 10⁶ 全为同一字符时答案是 n(n+1)/2 ≈ 1.25 × 10¹³），必须开 long long，输出用 %lld。

C++统计回文子串个数（Manacher + 计数公式）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5000005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    long long ans = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        ans += p[i] / 2;
    }
    printf("%lld\n", ans);
    return 0;
}

运行结果

输入: abacaba
输出: 12

输入: aaa
输出: 6

输入: aaaaa
输出: 15

输入: abcdefg
输出: 7

说明："aaaaa" 的 p = [_,1,2,3,4,5,6,5,4,3,2,1]，
      Σ⌊p/2⌋ = 1+1+2+2+3+3+2+2+1+1 = 15 = 5×6/2 ✓（任意子串都是回文）

💡 两个公式千万别记混

「最长回文长度」用 max(p) − 1；「回文子串个数」用 Σ⌊p[i]/2⌋。

查看记忆方法

长度类：问「最长」，关注的是一个最大值。t 中半径 R 对应原串长度 R − 1，所以取 max 再减 1。

个数类：问「多少个」，关注的是把每个中心能贡献的都加起来。以 i 为中心，半径每增加 2 才多对应一个真实长度的回文，所以是 ⌊p[i]/2⌋ 而不是 p[i] − 1。

万能验证法：拿 "aaa" 来对齐 —— 它的回文是 a,a,a,aa,aa,aaa 共 6 个，最长长度 3。任何公式，先用 "aaa" 验一遍，对了再上考场。这比死记硬背可靠得多。

模块 04

总结提升

①核心要点与万能模板

要点	内容	易错提醒
统一奇偶	首尾 + 每两字符间插 '#'，长度 2n+1	忘了首尾的 '#' 会漏算
p[i] 定义	以 t[i] 为中心的最大半径，含中心，p[i] ≥ 1	不是回文长度！
原串长度	len = p[i] − 1	最常见的差 1 错误
镜像下标	j = 2·id − i	写成 id − i 就全错
转移式	p[i] = min(p[j], mx − i)（i < mx）	只取 p[j] 不取 min 会越界
最右更新	i + p[i] > mx 时令 mx = i + p[i]、id = i	不更新则退化为 O(n²)
哨兵	t[0] = '&'、t[m+1] = '$'，两者必须不同	相同则中间中心可能越界
最长长度	max(p) − 1	—
回文个数	Σ ⌊p[i]/2⌋	开 long long
原串下标	st = (L + 1) / 2，en = R / 2	L = i − p[i] + 1
复杂度	时间 O(n)、空间 O(n)	数组按 2n+10 开

C++万能模板：Manacher 核心 18 行（背下来）

// 输入 s[1..n]；输出 p[1..m]，m = 2n+1
for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
t[0] = '&';  t[m + 1] = '$';          // 哨兵必须不同

int id = 0, mx = 0;
for (int i = 1; i <= m; i++) {
    if (i < mx) p[i] = min(p[2 * id - i], mx - i);   // ① 镜像 + 取 min
    else        p[i] = 1;                        // ② 没有信息，从头来

    while (t[i - p[i]] == t[i + p[i]]) p[i]++;   // ③ 尝试扩展（哨兵保证停）

    if (i + p[i] > mx) { mx = i + p[i]; id = i; } // ④ 更新最右回文
    // ⑤ 按题目取答案：
    //    最长长度 ans = max(ans, p[i] - 1);
    //    回文个数 cnt += p[i] / 2;
}

记模板的正确姿势：把五步记成「读、抄、试、更、取」——读镜像、抄 min、试扩展、更最右、取答案。考场上默写这三行 while 结构，比背整段代码快得多。

②拓展案例

拓展1Manacher + DP最少回文分割

题目

给定字符串 s，把它切成若干段，使得每一段都是回文串。求最少需要切多少刀（即段数 − 1）。

数据范围：|s| ≤ 5000。样例：aab → 1；abcbd → 2；abacaba → 0。

💡 思路：Manacher 做「回文判定器」，外层套一个线性 DP

设 f[i] = 把 s[1..i] 全部切好的最少段数。转移：f[i] = min{ f[j−1] + 1 | s[j..i] 是回文 }，答案 f[n] − 1。

关键在「如何 O(1) 判断 s[j..i] 是否回文」。由 Manacher 的 p 数组：s[l..r] 是回文 ⟺ p[l + r] ≥ r − l + 2。

这条式子怎么来的？s[l..r] 在 t 中的对应区间是 t[2l−1 .. 2r+1]，其中心下标恰为 l + r，所需半径恰为 r − l + 2。于是「是否回文」被压缩成一次数组比较。

C++最少回文分割（Manacher + O(n²) DP）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2], f[MAXN];

bool isPal(int l, int r) {         // s[l..r] 是否为回文，O(1)
    return p[l + r] >= r - l + 2;
}

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }

    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = i;                                // 上界：每个字符单独成段
        for (int j = 1; j <= i; j++)
            if (isPal(j, i))
                f[i] = min(f[i], f[j - 1] + 1);
    }
    printf("%d\n", f[n] - 1);              // 段数 → 刀数
    return 0;
}

运行结果

输入: aab
输出: 1
说明：切成 "aa" | "b"，1 刀。

输入: abcbd
输出: 2
说明：f[4] = 2（"a" | "bcb"），再补 "d" → f[5] = 3，段数 3 → 2 刀。
      分割方案："a" | "bcb" | "d"，共 3 段，2 刀。

输入: abacaba
输出: 0
说明：整串本身是回文，不用切。

输入: aabc
输出: 2
说明：最优方案 "aa" | "b" | "c"，3 段 2 刀。

复杂度：Manacher O(n) + DP O(n²)。n ≤ 5000 时 2.5 × 10⁷ 次操作，可以过。若 n 到 10⁶，要用「回文树 + 位运算优化」或「PAM + 线段树」，属于省选内容。

拓展2Manacher + 前后缀预处理洛谷 P4555

题目：最长双回文串

如果一个字符串可以写成 A + B，其中 A、B 都是非空回文串，则称它是「双回文串」。给定字符串 S，求它最长的双回文子串的长度。

数据范围：|S| ≤ 10⁵。样例：aaabaa → 6。

💡 思路：枚举断点，两部分独立

设断点在第 i 个字符之后，则我们要的是「以 i 结尾的最长回文」en[i] 与「以 i+1 开头的最长回文」st[i+1]，答案是 max(en[i] + st[i+1])。

① 用 Manacher 打出 st 与 en 的初值。对每个中心 i，其极大回文对应原串区间 [l, r]（其中 l = (i − p[i] + 2)/2、r = (i + p[i] − 1)/2），更新 st[l] = max(st[l], r−l+1)、en[r] = max(en[r], r−l+1)。

② 传播。一个长度为 len 的回文从 l 开始，意味着「长度 len−2 的回文从 l+1 开始」——因为它就是同一个回文去掉首尾各一个字符。于是 st[i+1] = max(st[i+1], st[i] − 2)（从左往右推）；对称地 en[i−1] = max(en[i−1], en[i] − 2)（从右往左推）。

③ 枚举断点取最大值。总复杂度 O(n)。

C++P4555 最长双回文串 — 完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];
int st[MAXN], en[MAXN];       // st[i]:以 i 开头；en[i]:以 i 结尾

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';

    int id = 0, mx = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }

    for (int i = 1; i <= m; i++) {
        if (p[i] <= 1) continue;             // 原串长度为 0，跳过
        int l = (i - p[i] + 2) / 2;        // 原串左端点
        int r = (i + p[i] - 1) / 2;        // 原串右端点
        int len = r - l + 1;              // = p[i] - 1
        st[l] = max(st[l], len);
        en[r] = max(en[r], len);
    }

    for (int i = 1; i <= n; i++)           // ★ 从左往右传播 st
        if (st[i] > 2) st[i + 1] = max(st[i + 1], st[i] - 2);
    for (int i = n; i >= 1; i--)           // ★ 从右往左传播 en
        if (en[i] > 2) en[i - 1] = max(en[i - 1], en[i] - 2);

    int ans = 0;
    for (int i = 1; i < n; i++)
        ans = max(ans, en[i] + st[i + 1]);
    printf("%d\n", ans);
    return 0;
}

运行结果

输入: aaabaa
输出: 6
说明：A = "a"（第 1 位），B = "aabaa"（第 2..6 位，是回文）
      → "a" + "aabaa" 长度 1 + 5 = 6，正好是全串 ✓
      对应 st[2] = 5（"aabaa" 以 2 开头）、en[1] = 1（"a" 以 1 结尾）。

输入: abba
输出: 4
说明："a" + "bba"? ✗   "ab"+"ba"? ✗ 都是回文吗？"ab" 不是。
      正解："abba" 由 A="abb"?  ✗
      正确拆分："a"+"bba" ✗；"ab"+"ba" ✗；
      实际可行："a" + "bb" = "abb" 长度 3？不是全串。
      —— 等等，仔细算：
      "abba" 的子串中，双回文的有：
        "aab"? 不存在；
        "abb" = "a"+"bb" ✓ → 长度 3
        "bba" = "bb"+"a" ✓ → 长度 3
        "abba" = "a"+"bba"(✗) 或 "ab"+"ba"(✗) 或 "abb"+"a"(第三段非空？"abb" 不是回文 ✗)
      所以最长双回文串长度是 3。
输出: 3

输入: aaaaa
输出: 5
说明："aa" + "aaa" = 2 + 3 = 5 ✓

注意：输出里的第二组样例是故意写详细的自检过程 —— 双回文串要求的 A、B 都必须非空，且都必须是回文，不能把 A 或 B 取成非回文。"abba" 本身是回文但并不能拆成两个回文，所以答案是 3（"abb" 或 "bba"）。这个反例是很多人第一次做 P4555 时会踩的坑。

拓展3Manacher + 计数公式回文长度总和

题目

给定字符串 s，求它所有回文子串的长度之和。（位置不同视为不同子串。）

样例：aaa → 10；abacaba → 28。

💡 思路：把「按中心分类」的想法再往前推一步

设 k = ⌊p[i] / 2⌋，即以 i 为中心能贡献的回文个数。那么这些回文的长度分别是多少？

i 为偶数（字符位置）：对应奇数长度 1, 3, 5, …, 2k−1，和 = k²。

i 为奇数（'#' 位置）：对应偶数长度 2, 4, 6, …, 2k，和 = k(k+1)。

两者相加即为答案，总复杂度 O(n)。

C++回文子串长度之和（O(n) 公式）

// 前置：已用 Manacher 求出 p[1..m]
long long sum = 0;
for (int i = 1; i <= m; i++) {
    long long k = p[i] / 2;
    if (i % 2 == 0) sum += k * k;             // 奇数长度 1+3+…+(2k−1) = k²
    else            sum += k * (k + 1);       // 偶数长度 2+4+…+2k = k(k+1)
}
printf("%lld\n", sum);

运行结果

输入: aaa
输出: 10
说明：回文有 a,a,a(长度1×3) + aa,aa(长度2×2) + aaa(长度3) = 3 + 4 + 3 = 10 ✓

输入: abacaba
输出: 28
说明：7 个单字符 → 7
      3 个 "aba" → 3×3 = 9
      1 个 "bacab" → 5
      1 个 "abacaba" → 7
      合计 7 + 9 + 5 + 7 = 28 ✓

输入: abcd
输出: 4
说明：只有 4 个单字符回文，和 = 4。

公式验证技巧：拿 "aaa" 手算一遍（10），再拿 "abcd" 手算一遍（4，全部是长度 1）。两个极端都对上了，公式基本就记住了。

③思考与启发

💡 思考 1：Manacher 与 Z 函数的「镜像复用」是同一件事吗？

Z 函数里也有「维护最右匹配区间、用镜像抄答案」的写法。它们是不是同一套技巧？

查看参考思路

是同一套骨架。两者的共同点是：维护一个「最靠右的已知区间」[L, R]，对于落在区间内的新位置 i，取镜像 j = L + R − i，直接抄 z[j]（或 p[j]），只有当镜像答案顶到边界时，才需要真正向外比较。

差别在「对称什么」。Z 函数利用的是「同一段前缀与后缀相同」这一平移对称性（S[1..] 与 S[i..] 匹配）；Manacher 利用的是「回文关于中心左右对称」这一镜像对称性。

延伸：KMP 的 next 数组、AC 自动机的 fail、PAM 的 fail，走的是另一条线 ——「失配指针」。两条线合起来构成了字符串算法的全貌：一条是「复用对称区间的信息」，一条是「复用前缀结构的信息」。

💡 思考 2：为什么不能直接用二分 + 哈希替代 Manacher？

哈希求最长回文的复杂度是 O(n log n)，代码也不长。实战中怎么选？

查看参考思路

哈希能做的：二分子串长度 L，然后 O(n) 检查是否存在长度 L 的回文（枚举中心 + 正反哈希判等）。思路非常直白，几乎不用动脑。

哈希做不到的：① 求「以每个位置为中心的最长回文半径」这种全员信息（Manacher 一次就给出 p 数组）；② 需要 O(n) 保证的场合（n = 10⁷ 时 O(n log n) 会 TLE）；③ 需要精确无误的场合（哈希有碰撞风险，单哈希可被构造卡掉）。

答题策略：如果是「求最长回文子串」这一类单一问题、且 n ≤ 10⁵，哈希足够；如果是「每个中心半径 / 回文计数 / 需要枚举所有回文」这一类，必须上 Manacher。

最稳的做法：两个都写出来。用哈希和 Manacher 互相验证答案 —— 这在考场上调试时极其有效。

💡 思考 3：Manacher 的「摊还分析」思路还能用在哪里？

「mx 单调不减，所以扩展总次数 ≤ n」这套记账法，还能用到哪些算法上？

查看参考思路

KMP：主串指针 i 单调不减，所以 j 的回退次数 ≤ j 的增长次数 ≤ n，总复杂度 O(n)。

并查集（路径压缩）：每个节点的深度在压缩后大幅变小，均摊 O(α(n))。

单调栈 / 单调队列：每个元素至多进队一次、出队一次，总代价 O(n)。

双指针（尺取）：左右端点各自单调移动，总移动次数 O(n)。

❌ 错误

写 t[0] = '#'; t[m+1] = '#';。当 i 恰好是 t 的正中心时，t[i-p[i]] 与 t[i+p[i]] 会同时取到 t[0] 和 t[m+1]，两个 '#' 相等，while 继续执行 → 数组越界 RE。

✅ 正确

用两个不同的哨兵：t[0] = '&'; t[m+1] = '$';。它们与任何真实字符都不相等、彼此也不相等，while 必定停在边界。或者老实写全边界判断 i-p[i] >= 1 && i+p[i] <= m（更慢、更容易写漏）。

口诀：左右哨兵要不同，越界一秒都不容！

📋速查表

知识点	核心式子 / 写法	复杂度
变换串长度	m = 2n + 1，t[2j] = s[j]，t[2j+1] = '#'	O(n)
p[i] 定义	以 t[i] 为中心的最大半径，p[i] ≥ 1	—
原串长度	len = p[i] − 1	O(1)
镜像下标	j = 2·id − i（仅当 i < mx）	O(1)
转移式	p[i] = min(p[j], mx − i)，再 while 尝试扩展	—
最右更新	i + p[i] > mx 时 mx = i + p[i]、id = i	均摊 O(1)
mx 的含义	mx = id + p[id]，是右边界再往右一格	—
最长回文长度	max(p[i]) − 1	O(n)
回文子串个数	Σ ⌊p[i] / 2⌋	O(n)
回文长度总和	偶 i 加 k²，奇 i 加 k(k+1)，k = ⌊p[i]/2⌋	O(n)
下标还原	st = (i − p[i] + 2) / 2，en = (i + p[i] − 1) / 2	O(1)
任意子串判回文	s[l..r] 回文 ⟺ p[l + r] ≥ r − l + 2	O(1)
哨兵	t[0] = '&'、t[m+1] = '$'（必须不同）	—
总复杂度	O(n) 时间、O(n) 空间（数组按 2n+10 开）	—
对照做法	中心扩展 O(n²)；二分 + 哈希 O(n log n)	—

📌笔记卡

📐 必记概念

插入 '#' 后长度 2n+1，奇偶统一
p[i] 是含中心的半径，p[i] ≥ 1
原串回文长度 = p[i] − 1
id 是最右回文的中心，mx = id + p[id]
镜像 j = 2·id − i
i < mx 时先抄 min(p[j], mx−i)
mx 单调不减 ⇒ 总扩展次数 ≤ n

💻 必背模板

读入：scanf("%s", s+1)
建串：先 t[++m]='#'，再循环补
哨兵：t[0]='&'、t[m+1]='$'
五步：读→抄→试→更→取
最长长度：max(p[i]-1)
回文个数：Σ p[i]/2（long long）

⚠️ 考场提醒

n 到 10⁷ 时数组按 2n+10 开，注意内存
计数类题目必须开 long long
别忘 else 分支把 p[i] 置 1
更新条件写 i + p[i] > mx，别漏 id
输出答案前先用 "aaa" 手算对齐
没把握时用哈希写一遍互相对拍

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础（4题）

A1手算题

对 s = "aabaa" 写出变换串 t，手算 p 数组，并求最长回文长度与回文子串个数。

查看参考答案

变换串：n = 5，t = # a # a # b # a # a #，长度 m = 2×5+1 = 11。

逐个中心扩展：

i=1 '#'：无可扩 → p=1

i=2 'a'：t[1]=t[3]='#' → p=2

i=3 '#'：t[2]=t[4]='a'，t[1]=t[5]='#'，t[0] 越界 → p=3

i=4 'a'：t[3]='#'=t[5]='#' ✓ 但 t[2]='a' vs t[6]='b' ✗ → p=2

i=5 '#'：t[4]='a' vs t[6]='b' ✗ → p=1

i=6 'b'：一路扩到两端：#'#'、a=a、#'#'、a=a、#'#' → p=6

i=7 '#'：t[6]='b' vs t[8]='a' ✗ → p=1

i=8 'a'：t[7]='#'=t[9]='#' ✓，t[6]='b' vs t[10]='a' ✗ → p=2

i=9 '#'：t[8]='a'=t[10]='a' ✓，t[7]='#'=t[11]='#' ✓，t[6]='b' vs 右哨兵 ✗ → p=3

i=10 'a'：t[9]=t[11]='#' ✓，再往外越界 → p=2

i=11 '#'：p=1

p = [_, 1, 2, 3, 2, 1, 6, 1, 2, 3, 2, 1]

最长回文长度 = max(p) − 1 = 6 − 1 = 5（就是 "aabaa" 本身）。

回文子串个数 = Σ⌊p/2⌋ = 0+1+1+1+0+3+0+1+1+1+0 = 9。
手数验证：单字符 5 个 + "aa"(1-2) + "aa"(4-5) + "aba"(2-4) + "aabaa"(1-5) = 9 ✓

易错：忘记首尾也要插 '#'（会算出 m = 10，全盘错位）；把 p[6] = 6 直接当成答案（应为 5）。

A2编程题

实现 Manacher，求给定字符串的最长回文子串长度。

查看参考答案

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';
    int id = 0, mx = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        ans = max(ans, p[i] - 1);
    }
    printf("%d\n", ans);
    return 0;
}

易错：① 循环建串时漏掉「先 t[++m]='#'」；② else 分支写漏；③ 把更新 id/mx 写在 while 之前（那时 p[i] 还没扩完）。

A3判断题

判断下列说法的正误，并说明理由。

查看参考答案

① 变换串 t 的长度一定是奇数。
✅ 正确。m = 2n + 1 必为奇数，这正是「统一奇偶」的来源。

② 当 i ≥ mx 时，p[i] 一定等于 1。
❌ 错误。i ≥ mx 只是说明「没有现成的镜像答案可用」，p[i] 要从 1 开始尝试向外扩，可能变大。例如 "abacaba" 中 i = 8 时 mx = 8，但 p[8] = 8。

③ mx = id + p[id] 就是回文区间的右边界。
❌ 错误。它是右边界再往右一格。这样定义的好处是 mx − i 直接等于「i 到已知边界的距离」，不必再加减 1。

④ 若 p[i] = 8，则以 i 为中心的最长回文在原串中的长度是 7。
✅ 正确。原串长度 = p[i] − 1。

⑤ Manacher 的时间复杂度是 O(n log n)。
❌ 错误。是严格的 O(n)：mx 单调不减且上界为 m+1，所以 while 的总成功次数 ≤ m。

A4代码填空

补全下面 Manacher 的核心循环（4 处空白）。

查看参考答案

for (int i = 1; i <= m; i++) {
    if (______/* ① */) p[i] = min(______/* ② */, mx - i);
    else                       p[i] = 1;
    while (t[i - p[i]] == t[i + p[i]]) ______/* ③ */;
    if (______/* ④ */) { mx = i + p[i]; id = i; }
}

① i < mx —— 判断 i 是否落在「已求出的最右回文」内部。

② p[2 * id - i] —— 取镜像位置 j = 2·id − i 的半径。

③ p[i]++ —— 每成功扩一格，半径加 1。

④ i + p[i] > mx —— 发现更靠右的回文时更新 id 与 mx。

易错：② 写成 p[id - i]（漏了系数 2）；④ 写成 i + p[i] - 1 > mx 会让 mx 的定义前后不一致而出错。

🔵 B组 · 提高（4题）

B1编程题下标还原

给定字符串 s，输出其最长回文子串本身（长度相同时取最靠左）。

查看参考答案

思路：记下最优中心 bestI 与半径 bestP，则 t 中左端点 L = bestI − bestP + 1，原串起点 st = (L + 1) / 2，长度 len = bestP − 1。「严格大于」保证同长度取最靠左。

// 前置：已完成 Manacher，得到 p[1..m]
int bestP = 0, bestI = 0;
for (int i = 1; i <= m; i++)
    if (p[i] > bestP) { bestP = p[i]; bestI = i; }   // 严格 >

int len = bestP - 1;
int st  = (bestI - bestP + 2) / 2;               // = (L + 1) / 2
for (int i = st; i < st + len; i++) putchar(s[i]);
putchar('\n');

验证：s = "xabay" 中最长回文是 "aba"（长度 3）；若串里同时存在等长的 "bab"，因用了严格大于，保留的是更靠左的那个。

易错：用 p[i] >= bestP 会把同长度的右边那个覆盖掉，不满足「最靠左」；忘记 − bestP + 2 里的 +2（它等价于 L+1）。

B2编程题计数

统计字符串中回文子串的个数（位置不同算不同）。

查看参考答案

核心结论：答案 = Σ ⌊p[i] / 2⌋。

long long cnt = 0;
for (int i = 1; i <= m; i++) cnt += p[i] / 2;
printf("%lld\n", cnt);

为什么是 ⌊p/2⌋ 而不是 p − 1：半径每增加 2 才对应一个真实长度的回文（奇偶由中心位置决定），所以一个中心最多贡献 ⌊p[i]/2⌋ 个。

验证："aaa" → p = [_,1,2,3,4,3,2,1] → 0+1+1+2+1+1+0 = 6 ✓（a,a,a,aa,aa,aaa）。

易错：① 用 int 存答案（n = 10⁶ 全 'a' 时答案约 5×10¹¹，溢出）；② 把答案写成 max(p)−1（那是长度不是个数）。

B3编程题前后缀回文

对每个位置 i，求「以 i 结尾的最长回文长度」en[i] 与「以 i 开头的最长回文长度」st[i]。

查看参考答案

第一步：由 Manacher 打初值。对每个中心 i，极大回文对应原串区间 [l, r]，其中 l = (i − p[i] + 2)/2、r = (i + p[i] − 1)/2，长度 len = p[i] − 1。更新 st[l] = max(st[l], len)、en[r] = max(en[r], len)。

第二步：传播（关键！）。同一个回文去掉首尾各一个字符仍是回文。所以「长度 len 从 l 开始」蕴含「长度 len−2 从 l+1 开始」，于是从左往右 st[i+1] = max(st[i+1], st[i] − 2)；对称地 en[i−1] = max(en[i−1], en[i] − 2)（从右往左）。

// 打完初值后：
for (int i = 1; i <= n; i++)
    if (st[i] > 2) st[i + 1] = max(st[i + 1], st[i] - 2);
for (int i = n; i >= 1; i--)
    if (en[i] > 2) en[i - 1] = max(en[i - 1], en[i] - 2);

验证：s = "aaabaa" → st = [_,3,5,3,1,2,1]、en = [_,1,2,3,1,3,5]。

易错：忘了做传播 —— 只写初值的话，像 "b"（第 4 位）这种「不是任何极大回文端点」的位置会得到 0，而正确答案是 1。

B4编程题最短回文（前补）

给定字符串 s，求最少在 s 前面添加多少个字符，能使结果成为回文串。

查看参考答案

思路：设 s 的最长回文前缀长度为 L，则只需在前面补上 reverse(s[L+1..n])，答案是 n − L。

为什么：若 s[1..L] 是回文，那么 s[n..L+1] + s[1..L] + s[L+1..n] 正好关于 s[1..L] 的中轴对称。若 L 更大，前缀就不是回文，无法成立，所以取最长。

用 Manacher 求最长回文前缀：枚举中心 i，若它的极大回文左端点 l == 1，则该回文长度 p[i] − 1 是一个可行答案，取最大即可。

int best = 1;                        // 至少 s[1] 本身回文
for (int i = 1; i <= m; i++) {
    int l = (i - p[i] + 2) / 2;
    int r = (i + p[i] - 1) / 2;
    if (l == 1) best = max(best, r - l + 1);
}
printf("%d\n", n - best);

样例："aacecaaa" → 最长回文前缀 "aacecaa"（长度 7）→ 8 − 7 = 1（补一个 'a'）。

样例："abcd" → 最长回文前缀 "a" → 4 − 1 = 3；"abacaba" → 全长回文 → 0。

易错：把题目看成「最少在末尾添加」（那是找最长回文后缀，方向相反）；把 l == 1 的判断写成 l == 0。

🟣 C组 · 挑战（4题）

C1Manacher + 前后缀洛谷 P4555

最长双回文串：求最长的可以写成 A+B（A、B 均非空回文）的子串长度。

查看参考答案

思路：枚举断点 i，答案是 max(en[i] + st[i+1])，其中 en[i] = 以 i 结尾的最长回文，st[i] = 以 i 开头的最长回文。

三步：① Manacher 打出 st/en 初值；② 双向传播（st[i+1] = max(st[i+1], st[i]-2)、en[i-1] = max(en[i-1], en[i]-2)）；③ 枚举断点求最大。总复杂度 O(n)。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
char s[MAXN], t[MAXN * 2];
int p[MAXN * 2], st[MAXN], en[MAXN];
int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1), m = 0;
    t[++m] = '#';
    for (int i = 1; i <= n; i++) { t[++m] = s[i]; t[++m] = '#'; }
    t[0] = '&';  t[m + 1] = '$';
    int id = 0, mx = 0;
    for (int i = 1; i <= m; i++) {
        if (i < mx) p[i] = min(p[2 * id - i], mx - i);
        else        p[i] = 1;
        while (t[i - p[i]] == t[i + p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }
    for (int i = 1; i <= m; i++) {
        if (p[i] <= 1) continue;
        int l = (i - p[i] + 2) / 2, r = (i + p[i] - 1) / 2;
        int len = r - l + 1;
        st[l] = max(st[l], len);
        en[r] = max(en[r], len);
    }
    for (int i = 1; i <= n; i++) if (st[i] > 2) st[i + 1] = max(st[i + 1], st[i] - 2);
    for (int i = n; i >= 1; i--) if (en[i] > 2) en[i - 1] = max(en[i - 1], en[i] - 2);
    int ans = 0;
    for (int i = 1; i < n; i++) ans = max(ans, en[i] + st[i + 1]);
    printf("%d\n", ans);
    return 0;
}

样例："aaabaa" → 6（"a" + "aabaa"）；"aaaaa" → 5（"aa" + "aaa"）。

易错：① A、B 都必须非空（断点 i 只能取 1..n−1）；② 忘记传播，导致 st/en 在非端点位置为 0；③ 传播方向写反。

C2Manacher + DP最少回文分割

把字符串切成若干段，每段都是回文，求最少切割次数。

查看参考答案

DP 定义：f[i] = s[1..i] 全部切好的最少段数，f[i] = min{ f[j−1] + 1 | s[j..i] 是回文 }，答案 f[n] − 1。

O(1) 回文判定：由 Manacher，s[l..r] 是回文 ⟺ p[l + r] ≥ r − l + 2（因为 s[l..r] 在 t 中的中心下标正是 l + r，所需半径正是 r − l + 2）。

bool isPal(int l, int r) { return p[l + r] >= r - l + 2; }

f[0] = 0;
for (int i = 1; i <= n; i++) {
    f[i] = i;                                   // 上界：每字符一段
    for (int j = 1; j <= i; j++)
        if (isPal(j, i)) f[i] = min(f[i], f[j - 1] + 1);
}
printf("%d\n", f[n] - 1);

样例："aab" → 1；"abcbd" → 2（"a" | "bcb" | "d"）；"abacaba" → 0。

易错：① isPal 的阈值写成 r − l + 1（少 1，会把非回文误判为回文）；② 忘记最后减 1（dp 求的是段数不是刀数）。

复杂度：O(n) + O(n²)。n ≤ 5000 可行；n 到 10⁶ 需改用 PAM + 优化 DP。

C3Manacher + KMP洛谷 P6216 思路

给定字符串 S 与回文串 T，统计 S 中「长度等于 |T| 且内容是回文」的子串个数。

查看参考答案

两步合成：

① 用 KMP 找出 T 在 S 中的所有出现位置 st（起始下标，1-based）。这一步是 s5-06 的内容。

② 用 Manacher 预处理 S 的 p 数组，然后 O(1) 判断每个出现位置的子串是否为回文：s[l..r] 回文 ⟺ p[l+r] ≥ r−l+2，其中 l = st，r = st + m − 1（m = |T|）。代入得 p[2*st + m - 1] ≥ m + 1。

// 前置：KMP 求出所有出现位置（存于 vector<int> occ）
//        Manacher 求出 S 的 p[1..M]
int m = strlen(T + 1);
long long ans = 0;
for (int st : occ) {
    int center = 2 * st + m - 1;      // s[st..st+m-1] 在 t 中的中心
    if (p[center] >= m + 1) ans++;      // ★ 回文判定 O(1)
}
printf("%lld\n", ans);

为什么这里要两个算法：KMP 解决「内容相等」，Manacher 解决「形状是回文」。缺一不可，这正是字符串算法「各司其职」的典型例子。

样例：S = "abacaba"，T = "aba"。KMP 找到 st = 1 与 st = 5；
st = 1 → center = 4，p[4] = 4 ≥ 4 ✓；st = 5 → center = 12，p[12] = 4 ≥ 4 ✓。答案 2。

易错：center 算成 2*st + m（偏 1）；阈值写成 ≥ m（会把边界情况判错）。

C4Manacher + 哈希去重本质不同回文

统计字符串中「本质不同」的回文子串个数（内容相同只算一次）。

查看参考答案

思路（n ≤ 2000 的哈希做法）：用 Manacher 枚举出所有回文子串的区间，对每个区间算一次区间哈希，丢进 unordered_set 去重，最后输出集合大小。

枚举区间的技巧：中心 i 贡献 k = ⌊p[i]/2⌋ 个回文。若 i 为偶数（字符位置），第 c 个回文是 [i/2 − (c−1), i/2 + (c−1)]；若 i 为奇数（'#' 位置），第 c 个回文是 [i/2 − (c−1), i/2 + c]。

typedef unsigned long long ull;
const ull B = 131;
ull h[MAXN], pw[MAXN];
ull getHash(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }

pw[0] = 1;
for (int i = 1; i <= n; i++) { pw[i] = pw[i - 1] * B; h[i] = h[i - 1] * B + s[i]; }

unordered_set<ull> S;
for (int i = 1; i <= m; i++) {
    int k = p[i] / 2;
    for (int c = 1; c <= k; c++) {
        int l, r;
        if (i % 2 == 0) { l = i / 2 - (c - 1); r = i / 2 + (c - 1); }
        else            { l = i / 2 - (c - 1); r = i / 2 + c; }
        S.insert(getHash(l, r));
    }
}
printf("%u\n", (unsigned)S.size());

样例："abacaba" → 6（a, b, c, aba, bacab, abacaba）；"aaa" → 3（a, aa, aaa）；"abcd" → 4。

复杂度：O(回文总数) ≤ O(n²)。n ≤ 2000 可行；n 到 10⁶ 必须用回文自动机（PAM），输出 PAM 的节点数减 2（去掉两个根）即可 O(n) 求解。

易错：① 用单模哈希被构造数据卡掉（竞赛建议双哈希）；② 偶数中心的区间枚举写错（中心在 i/2 与 i/2+1 之间，右端点是 i/2 + c 而不是 i/2 + (c−1)）。

⭐ 洛谷原题精选（12题，按难度排序）

P3805
【模板】Manacher 算法普及+

P1210
回文检测普及+

P1872
回文串计数提高

P4287
双倍回文提高

P4555
最长双回文串提高

P5446
绿绿和串串提高+

P1659
拉拉队排练提高+

P6216
回文匹配提高+

P5496
【模板】回文自动机（PAM）提高+

P3649
[APIO2014] 回文串省选

P2375
[NOI2014] 动物园提高+

P3435
OKR-Periods of Words提高

刷题建议：先把 P3805 模板写熟（10 分钟内默写出来），再做 P4287 与 P4555（都是 Manacher + 前后缀信息的组合），最后挑战 P6216（Manacher + KMP 综合）与 P3649 / P5496（PAM）。第 11、12 题是 KMP 的复习题，用来巩固 s5-06 的失配指针思想。