📖 第 9.4 章：Manacher 与 Z 函数 ⏱️ 约 30 分钟 🥇 Gold

📖 第 9.4 章：Manacher 与 Z 函数

🎯 学习目标

学完本章后，你将能够：

用 Manacher 算法 O(N) 求最长回文子串并统计回文个数
理解 Z 函数（扩展 KMP）的定义与线性求法
掌握两者共享的「维护最右已知区间 + 镜像加速」思想

9.4.0 问题引入

本章解决两个看似不同、实则同源的问题：

问题 A（最长回文）： 给定字符串 s（长度 ≤ 10⁶），求最长回文子串的长度。

s = "abababa"  → 7
s = "abababc"  → 5（"ababa"）

问题 B（前缀匹配）： 给定模式串 P 和文本 T，统计有多少个位置 i，使得 P 与 T 从 i 开始的后缀的前 |P| 个字符完全匹配。

P = "aba", T = "ababa"   → 2（i = 0 和 i = 2）

问题 A 的朴素做法（中心扩展）是 O(N²)，问题 B 的朴素做法（逐位置比较）也是 O(N²)。有趣的是，两者的线性解法——Manacher 与 Z 函数——用了完全相同的策略：维护一个「当前已知的最靠右的区间」，新位置的答案先从区间内的镜像位置照搬，不够再暴力扩展。学完一个，另一个就是换了个定义照抄。

9.4.1 Manacher 算法——O(N) 最长回文

从中心扩展说起：O(N²) 为什么超时

「求字符串 s 的最长回文子串」有一个经典做法：枚举每个中心，向两边扩展。回文串有两种中心——某个字符（奇数长度，如 "aba" 中心是 b）或某两个字符之间的空隙（偶数长度，如 "abba" 中心是两个 b 之间）。每种中心最坏扩展 O(N)，总共 O(N) 个中心，复杂度 O(N²)。

当 N = 10⁶ 时（很多题就是这个量级），O(N²) 会达到 10¹² 次操作，必然超时。1975 年 Manacher 提出的算法把它降到了 O(N)。

技巧一：插入 '#' 统一奇偶

奇偶两种中心要写两份几乎相同的代码，容易出错。解决办法：在每两个字符之间以及首尾都插入分隔符 #。

原串：  a  b  a  b  a  b  c
新串：# a # b # a # b # a # b # c #

新串长度变成 2N+1（一定是奇数），所有回文的中心都变成了一个字符：

原串的奇回文 "aba" → 新串 #a#b#a#，中心是 b
原串的偶回文 "abba" → 新串 #a#b#b#a#，中心是 #

从此只需要处理「奇数长度」这一种情况。

p[i] 的定义与关键性质

设新串为 t，定义 p[i] = 以 t[i] 为中心的最长回文的半径（回文串为 t[i-p[i]+1 .. i+p[i]-1]，即 p[i] 是「包括中心在内往右延伸的字符数」）。

一个重要结论：在原串中，以某位置为中心的最长回文长度 = 新串中对应位置的 p[i] - 1。例如 "abababc" 中新串中心在 t[7]=a（原串下标 3）处 p=6，对应原串回文 "ababa"，长度 5 = 6-1。

朴素做法对每个 i 从半径 1 开始扩展，浪费了大量已经算出的信息。Manacher 的核心是利用已知回文的镜像加速。

维护当前右端点最靠右的回文串，记其中心为 id、右边界为 mx。当计算 p[i] 时，若 i < mx，说明 i 在这个大回文内部。设 j = 2*id-i 是 i 关于 id 的镜像位置，则：

p[i] ≥ min(p[j], mx - i)

为什么？

若以 j 为中心的回文完全落在大回文内部（p[j] < mx-i），由对称性，以 i 为中心的回文至少和它一样长，直接 p[i] = p[j]，一步都不用扩展；
若以 j 为中心的回文顶到了大回文的边界（p[j] ≥ mx-i），超出部分没有对称性保证，只能确定 p[i] ≥ mx-i，之后从 mx-i 开始继续中心扩展。

若 i ≥ mx，没有任何信息可用，老老实实从半径 1 开始扩展。

为什么是 O(N)？注意每次中心扩展成功（while 循环多走一步），mx 都会随之向右移动至少 1，而 mx 从不减小、最多移动 N 次。所以所有扩展的总步数是 O(N)。

完整实现（含哨兵）

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

// Manacher：O(N) 求最长回文子串长度
// 原串中以某位置为中心的最长回文长度 = 新串对应位置的 p[i] - 1
pair<string, vector<int>> manacher(const string& s) {
    // 1. 构造 "$#a#b#...#c#"：开头 '$' 哨兵防越界，'#' 统一奇偶
    string t = "$#";
    for (char c : s) { t += c; t += '#'; }
    t += '^';  // 结尾哨兵
    int n = t.size();
    vector<int> p(n, 0);

    // 2. 维护当前右边界最靠右的回文串（中心 id，右端 mx）
    for (int i = 1, id = 0, mx = 0; i < n - 1; i++) {
        // 镜像加速：i 在大回文内部时，借用镜像位置 2*id-i 的信息
        p[i] = (mx > i) ? min(p[2 * id - i], mx - i) : 1;
        // 中心扩展（哨兵保证不越界：'$' 和 '^' 必不相等且不等于其它字符）
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        // 更新最右回文
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }
    return {t, p};
}

int longest_palindrome(const string& s) {
    auto [t, p] = manacher(s);
    int best = 0;
    for (int i = 1; i < (int)t.size() - 1; i++) best = max(best, p[i] - 1);
    return best;
}

int main() {
    cout << longest_palindrome("abababa") << endl;  // 输出 7
    cout << longest_palindrome("abababc") << endl;  // 输出 5（"ababa"）
    cout << longest_palindrome("cbbd") << endl;     // 输出 2（"bb"）
    return 0;
}

逐步追踪：`"abababc"`

新串 t = $#a#b#a#b#a#b#c#^（下标 1..15 为有效部分）：

i :   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
t[i]: $  #  a  #  b  #  a  #  b  #  a  #  b  #  c  #  ^（1..15 为有效部分）
p[i]: 1  2  1  4  1  6  1  6  1  4  1  2  1  2  1

几个关键位置：

i=4（字符 b）：扩展得 #a#b#a#，p=4，回文右端到 i+p-1=7。更新 mx=8? 不——右边界是 i+p=8，即 mx=8，id=4；
i=7（字符 a）：在 [0,8] 内，镜像 j=1，min(p[1], 8-7)=1，从 1 扩展得 #b#a#b#a#b#，p=6，mx 更新为 13，id=7；
i=9（字符 b）：在 [1,13] 内，镜像 j=5，min(p[5]=1, 13-9)=1，扩展得 #a#b#a#b#a#，p=6；
i=11（字符 a）：镜像 j=3，min(p[3]=1, ...) =1，扩展得 p=4；
i=13（字符 b）：镜像 j=1，但 13 已顶到 mx，从 min(p[1]=2, 13-13+...) 开始，扩展得 #a#b#，p=2。

最大 p 值为 6，最长回文长度 = 6-1 = 5，即 "ababa"。

开头放 '$'、结尾放 '^'（两个都不属于原字符集、且互不相同）不是装饰：while (t[i+p[i]] == t[i-p[i]]) 故意不写下标检查。若没有哨兵，i 靠近边界时 i-p[i] 会越界到 -1、i+p[i] 会越界到 n，产生未定义行为；有了哨兵，扩展到哨兵位置必然失配停下。这是 Manacher 代码既短又快的关键——但前提是哨兵字符绝不能出现在原串中。

例题：回文子串计数

问题：统计字符串 s 中回文子串的个数（子串按位置区分，如 "aaa" 有 6 个：3 个 "a"、2 个 "aa"、1 个 "aaa"）。

思路：以每个位置为中心的回文串个数恰好是 p[i] / 2（新串中半径 p[i] 的回文，对应原串中 p[i]/2 个回文：从最长的开始每次长度减 2）。把所有中心加起来即可，复杂度 O(N)。

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

long long count_palindromes(const string& s) {
    string t = "$#";
    for (char c : s) { t += c; t += '#'; }
    t += '^';
    int n = t.size();
    vector<int> p(n, 0);
    for (int i = 1, id = 0, mx = 0; i < n - 1; i++) {
        p[i] = (mx > i) ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
    }
    long long ans = 0;
    for (int i = 1; i < n - 1; i++) ans += p[i] / 2;
    return ans;
}

int main() {
    cout << count_palindromes("abababc") << endl;  // 输出 13
    cout << count_palindromes("aaa") << endl;      // 输出 6
    cout << count_palindromes("abc") << endl;      // 输出 3
    return 0;
}

验证 "abababc"：单字符 7 个 + "aba"/"bab" 共 4 个 + "ababa"/"babab" 共 2 个 = 13 ✓。

9.4.2 Z 函数（扩展 KMP）

引入：另一种「自我匹配」

回忆第 9.2 章的前缀函数：π[i] 描述的是**「以 i 结尾的后缀」与「整个串的前缀」**的最长匹配。现在换一个视角——我们不看「以 i 结尾的」，而看「以 i 开头的」：

z[i] = 后缀 s[i..n-1] 与整个串 s 的最长公共前缀（LCP）的长度，规定 z[0] = 0（或 n，看实现约定，本书取 0）。

对比一下：

π[i]：s 的前缀 vs s[0..i] 的后缀——「前缀 vs 后缀」
z[i]：s 的前缀 vs s[i..] 的前缀——「前缀 vs 前缀」

两者信息等价（可以 O(N) 互相推导），但 Z 函数的定义更直观：z[i] 就是「从 i 开始往后，能和串开头匹配多长」。

几个例子（下标从 0 开始）：

z("aaaaa")  = [0, 4, 3, 2, 1]
z("aaabaab") = [0, 2, 1, 0, 2, 1, 0]
z("abacaba") = [0, 0, 1, 0, 3, 0, 1]

比如 "abacaba"：z[4]=3，因为从下标 4 开始的后缀 "aba" 恰好与原串前缀 "aba" 匹配 3 个字符。

Z-box 与线性算法

朴素做法对每个 i 从 0 开始逐字符比较，最坏 O(N²)（如 "aaaaa"）。加速的思路和 Manacher 惊人地相似：维护已经匹配到的最右端，利用已算出的信息。

称区间 [i, i+z[i]-1] 为 i 的匹配段（Z-box）。算法过程中维护右端点最靠右的 Z-box，记为 [l, r]——它的含义是：s[l..r] 与 s 的前缀完全相同。

计算 z[i] 时（i 从 1 到 n-1）：

若 i < r：i 落在 Z-box 内。由 s[l..r] = s[0..r-l]，位置 i 在 box 内对应于前缀中的位置 i-l，因此
```
z[i] ≥ min(z[i-l], r - i)
```
- 若 z[i-l] < r-i：以 i-l 为中心的匹配段没有顶到 box 右端，整个信息可以照搬，z[i] = z[i-l]，一步不用比较；
- 否则只能确定 z[i] ≥ r-i，从 r-i 开始暴力扩展。
若 i ≥ r：没有信息，从 0 开始暴力扩展。

算出 z[i] 后，若 i + z[i] > r，更新 l = i, r = i + z[i]。

复杂度：暴力扩展每成功一步，r 就向右移至少 1，而 r 只增不减且不超过 n，所以总扩展次数 O(N)，整体 O(N)。

完整实现

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

// Z 函数（扩展 KMP）：z[i] = s 与 s[i..] 的最长公共前缀长度，z[0] = 0
vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        // i 在 Z-box [l,r) 内：借用镜像位置 i-l 的 z 值
        if (i < r) z[i] = min(r - i, z[i - l]);
        // 暴力扩展
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        // 更新最右 Z-box
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

int main() {
    for (const string& s : {"aaaaa", "aaabaab", "abacaba"}) {
        auto z = z_function(s);
        cout << s << ": ";
        for (int x : z) cout << x << " ";
        cout << endl;
    }
    return 0;
}

输出：

aaaaa: 0 4 3 2 1
aaabaab: 0 2 1 0 2 1 0
abacaba: 0 0 1 0 3 0 1

逐步追踪：`"aaaaa"`

i=1: i>r(r=0)，暴力扩展：s[0..3] vs s[1..4] 全匹配，z[1]=4。
     更新 l=1, r=5。
i=2: i<r，z[2] = min(5-2, z[1]=4) = 3。i+z[2]=5 不大于 r=5，不再扩展。
i=3: i<r，z[3] = min(5-3, z[2]=3) = 2。
i=4: i<r，z[4] = min(5-4, z[3]=2) = 1。

结果 [0,4,3,2,1]——注意 i≥2 之后一次比较都没做，全部靠镜像直接照搬。

与 KMP 对照

	前缀函数（KMP，第 9.2 章）	Z 函数（扩展 KMP）
定义	π[i] = s[0..i] 的最长 border（前缀 = 后缀）	z[i] = s[i..] 与 s 的最长公共前缀
视角	以 i 结尾的匹配	以 i 开头的匹配
维护的区间	「失配指针」链 π[π[...]]	最右 Z-box [l, r]
求模式串出现	拼接 `P#T`，找 π[i] = \|P\|	拼接 `P#T`，找 z[i] = \|P\|
复杂度	O(N)	O(N)
适用偏好	失配跳转、border 树上做 DP	「每个后缀 vs 前缀」的直观统计

经验法则：题目若问「后缀与前缀的关系」（如最短周期 i + z[i] == n、后缀匹配计数），Z 函数往往写起来更直白；若要在 border 链上做递推 DP，KMP 的 π 数组更顺手。

例题：border 式匹配计数

问题：给定模式串 P 和文本 T（|P|, |T| ≤ 10⁶），求 T 中有多少个位置 i，使得 T 从 i 开始的后缀以 P 为前缀（即 P 与 T 的该后缀的前 |P| 个字符完全匹配）。

思路：和 KMP 匹配一样用拼接技巧。构造 s = P + '#' + T，求 Z 函数。对 T 的每个起点 i，对应 s 中下标 i + |P| + 1，若 z[i+|P|+1] == |P|，则该位置匹配。分隔符 '#' 保证 z 值不会「穿过」边界（P 和 T 中都不含 '#'）。复杂度 O(|P| + |T|)。

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

vector<int> z_function(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) { l = i; r = i + z[i]; }
    }
    return z;
}

long long count_matches(const string& P, const string& T) {
    auto z = z_function(P + '#' + T);
    int m = P.size();
    long long cnt = 0;
    for (int i = m + 1; i < (int)z.size(); i++)
        if (z[i] == m) cnt++;
    return cnt;
}

int main() {
    cout << count_matches("ab", "ababab") << endl;   // 输出 3（下标 0、2、4）
    cout << count_matches("aba", "ababa") << endl;   // 输出 2（下标 0、2）
    cout << count_matches("xyz", "abcabc") << endl;  // 输出 0
    return 0;
}

⚠️ 常见错误

错误	原因	修复方案
Manacher 哨兵缺失或与原字符冲突	`while` 循环不检查下标，越界为未定义行为	开头放 `'$'`、结尾放 `'^'`，且保证不在原串中出现
Manacher 忘记回文长度 = p[i] - 1	新串长度 2N+1，半径换算回来要减 1	记住结论：原串回文长度 = p[i] - 1
Z 函数边界用 `i <= r` 且照搬时多扩展	z[i-l] 顶到 box 右端时照搬结果错误	用 `i < r`（r 为开区间端点）或在 `z[i-l] < r-i` 时才直接赋值
z[0] 约定混乱	有的实现取 z[0]=n，有的取 0	全书统一取 z[0] = 0，拼接匹配从下标 m+1 开始找
拼接时分隔符出现在 P 或 T 中	z 值可能穿过边界导致错误匹配	选字符集中不存在的分隔符

💪 练习题（本章 2 道，全部含完整解答）

🟡 进阶练习

题目 1：最长回文子串
给定字符串 s（长度 ≤ 10⁶），求最长回文子串的长度。要求 O(N)。

示例：

s = "abababa"  → 7
s = "abababc"  → 5（"ababa"）

思路： Manacher 算法。插入 # 统一奇偶后求半径数组 p，答案为 max(p[i]) - 1。

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

int main() {
    string s; cin >> s;
    string t = "$#";
    for (char c : s) { t += c; t += '#'; }
    t += '^';
    int n = t.size();
    vector<int> p(n, 0);
    int best = 0;
    for (int i = 1, id = 0, mx = 0; i < n - 1; i++) {
        p[i] = (mx > i) ? min(p[2 * id - i], mx - i) : 1;
        while (t[i + p[i]] == t[i - p[i]]) p[i]++;
        if (i + p[i] > mx) { mx = i + p[i]; id = i; }
        best = max(best, p[i] - 1);
    }
    cout << best << "\n";
    return 0;
}

🔴 挑战练习

题目 2：两字符串 border 计数
给定字符串 P 和 T（长度 ≤ 10⁶），统计有多少个位置 i（0 ≤ i < |T|），使得 P 恰好是「T 从 i 开始的后缀」的前缀（即 P 与 T[i..i+|P|-1] 完全匹配）。要求 O(|P| + |T|)。