第十三章 字符串算法¶
字符串是计算机科学中最基本的数据类型之一。在 ACM 竞赛中，字符串问题涉及模式匹配、回文检测、子串统计等经典场景。掌握字符串哈希、KMP、Trie、Manacher 等核心算法，是解决中高难度竞赛题的关键基础。
13.1 字符串哈希¶
13.1.1 基本思想¶
字符串哈希将一个字符串映射为一个整数值（哈希值），使得我们可以用 O(1) 的时间比较两个子串是否相等。这是许多字符串算法的基石。
多项式哈希的定义如下：
其中：
- \(s[i]\) 是字符串第 \(i\) 个字符的编码值（通常用 ASCII 码）
- \(P\) 是一个选定的进制基数（通常取质数，如 131、13331）
- \(M\) 是一个大质数模数（如 \(10^9 + 7\) 或 \(2^{64}\)）
- \(n\) 是字符串长度
graph LR
subgraph 多项式哈希计算示意 - 字符串 "abc"
A["a * P^2"] --> D["求和取模"]
B["b * P^1"] --> D
C["c * P^0"] --> D
D --> E["h('abc')"]
end13.1.2 前缀哈希与子串哈希¶
直接对每个子串计算哈希的时间是 O(n) 的。为了实现 O(1) 子串哈希查询，我们预计算前缀哈希数组。
前缀哈希的定义：
注意这里 \(H[i]\) 表示前 \(i\) 个字符（即 \(s[0..i-1]\)）的哈希值。
子串哈希公式： 子串 \(s[l..r]\)（从下标 \(l\) 到 \(r\)，包含两端）的哈希值为：
这样，任意子串的哈希值可以在 O(1) 时间内计算出来。
下标约定
本节公式采用 0 下标（\(l\)、\(r\) 从 0 计起）；而 13.1.4 的代码模板将字符串存成下标从 1 开始，对应公式变为 \(\text{hash}(l, r) = (H[r] - H[l-1] \cdot P^{r-l+1}) \bmod M\)。两者只差一个偏移，套用时注意换算。
13.1.3 双哈希¶
单哈希存在哈希冲突的风险——两个不同的字符串可能产生相同的哈希值。在竞赛中，为了降低冲突概率，通常使用双哈希：选取两组不同的 \((P, M)\) 对，计算两个哈希值。只有当两个哈希值都相等时，才认为字符串相等。
graph TD
subgraph 双哈希判定流程
A["字符串 S1, S2"] --> B["计算哈希1 (P1=131, M1=1e9+7)"]
A --> C["计算哈希2 (P2=13331, M2=1e9+9)"]
B --> D{"哈希1 相等?"}
C --> E{"哈希2 相等?"}
D -->|否| F["S1 != S2"]
E -->|否| F
D -->|是| G{"哈希2 相等?"}
G -->|是| H["S1 == S2（大概率）"]
G -->|否| F
end13.1.4 完整代码实现¶
注意：本模板采用 1 下标（读入后在字符串前补一个占位字符），与 13.1.2 节的 0 下标公式相差一个偏移，子串公式相应变为 \(h[r] - h[l-1] \cdot p[r-l+1]\)。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// ==================== 单哈希版本 ====================
const int P = 131; // 进制基数，选一个质数
const long long M = 1e9 + 7; // 模数，选一个大质数
const int MAXN = 1000010; // 字符串最大长度
long long h[MAXN]; // 前缀哈希数组
long long p[MAXN]; // P 的幂次数组，p[i] = P^i mod M
// 预计算前缀哈希和幂次数组
// s: 输入字符串（下标从 1 开始存储）
// n: 字符串长度
void buildHash(const string& s, int n) {
h[0] = 0;
p[0] = 1;
for (int i = 1; i <= n; i++) {
// 前缀哈希递推: h[i] = h[i-1] * P + s[i]
h[i] = (h[i - 1] * P % M + s[i]) % M;
// 幂次递推: p[i] = p[i-1] * P
p[i] = p[i - 1] * P % M;
}
}
// 计算子串 s[l..r] 的哈希值（下标从 1 开始）
// 时间复杂度: O(1)
long long getHash(int l, int r) {
// hash(l, r) = h[r] - h[l-1] * p[r-l+1]
long long res = (h[r] - h[l - 1] * p[r - l + 1] % M + M) % M;
return res;
}
// ==================== 双哈希版本 ====================
// 使用两组 (P, M) 对，降低冲突概率
// 注意：本结构体含 4 个长度为 MAXN 的 long long 数组，约 32MB，
// 必须定义为全局变量或 static；在函数内局部实例化会直接爆栈（栈一般只有 1~8MB）
struct DoubleHash {
static const int P1 = 131, P2 = 13331;
static const long long M1 = 1e9 + 7, M2 = 1e9 + 9;
long long h1[MAXN], h2[MAXN]; // 两组前缀哈希
long long p1[MAXN], p2[MAXN]; // 两组幂次
// 构建双哈希数组
void build(const string& s, int n) {
h1[0] = h2[0] = 0;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; i++) {
h1[i] = (h1[i - 1] * P1 % M1 + s[i]) % M1;
h2[i] = (h2[i - 1] * P2 % M2 + s[i]) % M2;
p1[i] = p1[i - 1] * P1 % M1;
p2[i] = p2[i - 1] * P2 % M2;
}
}
// 返回子串 s[l..r] 的双哈希值，用 pair 存储
pair<long long, long long> get(int l, int r) {
long long hash1 = (h1[r] - h1[l - 1] * p1[r - l + 1] % M1 + M1) % M1;
long long hash2 = (h2[r] - h2[l - 1] * p2[r - l + 1] % M2 + M2) % M2;
return {hash1, hash2};
}
// 判断两个子串是否相等
// 子串1: s1[l1..r1], 子串2: s2[l2..r2]
bool equal(int l1, int r1, int l2, int r2) {
return get(l1, r1) == get(l2, r2);
}
};
// ==================== 使用示例 ====================
int main() {
string s;
cin >> s;
int n = s.size();
// 在字符串前补一个字符，使下标从 1 开始
s = " " + s;
buildHash(s, n);
// 查询子串 s[l..r] 是否与 s[l2..r2] 相等
int q;
cin >> q;
while (q--) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (getHash(l1, r1) == getHash(l2, r2)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
时间复杂度分析：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 预处理（构建前缀哈希） | O(n) | 遍历一次字符串 |
| 查询子串哈希 | O(1) | 利用前缀哈希公式直接计算 |
| 比较两个子串是否相等 | O(1) | 比较哈希值 |
| 双哈希额外开销 | 常数倍 | 空间和时间均翻倍 |
| 操作 | 空间复杂度 | 说明 |
|---|---|---|
| 单哈希 | O(n) | 存储前缀哈希和幂次数组 |
| 双哈希 | O(n) | 存储两组前缀哈希和幂次数组 |
如何选择 P 和 M 的值
- P 的选择：通常取大于字符集大小的质数。对于小写字母（字符集大小 26），可以选 131、13331、19260817 等。P 越大，冲突概率越低。
- M 的选择：推荐使用大质数，如 \(10^9 + 7\)、\(10^9 + 9\)。也可以使用
unsigned long long自然溢出（等价于对 \(2^{64}\) 取模），速度更快，但需要注意被刻意构造数据卡掉的风险。 - 双哈希的必要性：在正式比赛中，单哈希被卡掉的情况时有发生。使用双哈希可以极大地降低冲突概率，是更稳妥的做法。
大数组必须定义为全局或 static
DoubleHash 结构体内含 4 个长度为 MAXN 的 long long 数组，约 32MB（h[]、p[] 等全局大数组同理）。这类对象必须定义为全局变量或 static：函数内的局部变量分配在栈上，而栈空间通常只有 1~8MB，局部实例化会直接爆栈（表现为 RE / Segmentation Fault）。
字符串哈希的局限
字符串哈希是概率性算法，理论上存在哈希冲突的可能（虽然双哈希后概率极低）。如果题目要求绝对正确的答案（如判定两个字符串是否相等），需要结合其他方法验证。此外，哈希值的大小依赖于字符编码，不同编码方式可能导致不同的哈希结果。
13.2 KMP 算法¶
13.2.1 问题定义¶
字符串匹配问题：给定一个长度为 \(n\) 的文本串 text 和一个长度为 \(m\) 的模式串 pattern，找出 pattern 在 text 中所有出现的位置。
朴素算法的思路是：对于 text 中的每个位置，逐字符比较是否与 pattern 匹配。最坏时间复杂度为 \(O(n \cdot m)\)。
KMP（Knuth-Morris-Pratt）算法通过预处理模式串，构建一个next 数组（也叫前缀函数 \(\pi\)），使得匹配过程中可以跳过不必要的比较，将时间复杂度降至 \(O(n + m)\)。
13.2.2 next 数组（前缀函数）¶
定义：对于模式串 \(p\)，\(\pi[i]\) 表示子串 \(p[0..i]\) 中，最长的既是真前缀又是真后缀的长度。
具体来说，\(\pi[i]\) 是满足以下条件的最大 \(k\)： - \(p[0..k-1] = p[i-k+1..i]\) - \(k < i + 1\)（即真前缀/真后缀，不能是整个子串本身）
以模式串 "ABABAC" 为例：
| 下标 i | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 字符 | A | B | A | B | A | C |
| π[i] | 0 | 0 | 1 | 2 | 3 | 0 |
推导过程：
- \(\pi[0] = 0\)：单个字符没有真前缀/真后缀
- \(\pi[1] = 0\)：子串 "AB"，前缀 "A" != 后缀 "B"
- \(\pi[2] = 1\)：子串 "ABA"，前缀 "A" == 后缀 "A"，长度 1
- \(\pi[3] = 2\)：子串 "ABAB"，前缀 "AB" == 后缀 "AB"，长度 2
- \(\pi[4] = 3\)：子串 "ABABA"，前缀 "ABA" == 后缀 "ABA"，长度 3
- \(\pi[5] = 0\)：子串 "ABABAC"，没有匹配的前缀后缀
graph TD
subgraph next 数组构建过程 - 模式串 "ABABAC"
A["i=0, π[0]=0: 'A' 无真前后缀"]
B["i=1, π[1]=0: 'AB', 'A' ≠ 'B'"]
C["i=2, π[2]=1: 'ABA', 'A'='A' (长1)"]
D["i=3, π[3]=2: 'ABAB', 'AB'='AB' (长2)"]
E["i=4, π[4]=3: 'ABABA', 'ABA'='ABA' (长3)"]
F["i=5, π[5]=0: 'ABABAC', 无匹配"]
A --> B --> C --> D --> E --> F
end13.2.3 next 数组的构建¶
构建 next 数组的核心思想是：利用已经计算好的 \(\pi[0..i-1]\) 来推导 \(\pi[i]\)，避免重复计算。
graph TD
subgraph next数组构建的递推过程
A["设 j = π[i-1]（上一个位置的最长前后缀长度）"] --> B{"p[i] == p[j]?"}
B -->|是| C["π[i] = j + 1"]
B -->|否| D["j = π[j-1]（回退到更短的前缀）"]
D --> B
C --> E["处理下一个位置 i+1"]
end13.2.4 KMP 匹配过程¶
当文本串中某位字符与模式串不匹配时，利用 next 数组跳转到模式串中合适的位置，避免从头开始比较。
graph LR
subgraph KMP匹配 - 跳过已匹配部分
A["text: ...ABABABAC..."] --> B["匹配 'ABAB' 后, text[4]='B'≠pattern[4]='A'"]
B --> C["查 next 数组: next[3]=2"]
C --> D["将 pattern 右移, 从 pattern[2]='A' 继续比较"]
end13.2.5 完整代码实现¶
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MAXN = 1000010;
int nxt[MAXN]; // next 数组（前缀函数）
int n, m; // n: 文本串长度, m: 模式串长度
// ==================== 构建 next 数组 ====================
// p: 模式串（下标从 0 开始）
// m: 模式串长度
// 时间复杂度: O(m)
void buildNext(const string& p, int m) {
nxt[0] = 0; // 第一个字符的 next 值为 0
// j 记录当前最长匹配的前缀末尾位置
for (int i = 1, j = 0; i < m; i++) {
// 如果 p[i] 不匹配 p[j]，不断回退 j
while (j > 0 && p[i] != p[j]) {
j = nxt[j - 1];
}
// 如果 p[i] == p[j]，匹配长度加 1
if (p[i] == p[j]) {
j++;
}
nxt[i] = j; // 记录 π[i]
}
}
// ==================== KMP 搜索 ====================
// s: 文本串（下标从 0 开始）
// p: 模式串（下标从 0 开始）
// 返回: 模式串在文本串中所有出现的起始位置
// 时间复杂度: O(n + m)
vector<int> kmpSearch(const string& s, const string& p) {
n = s.size();
m = p.size();
buildNext(p, m);
vector<int> matches; // 存储匹配位置
// i: 文本串指针, j: 模式串指针
for (int i = 0, j = 0; i < n; i++) {
// 当 s[i] != p[j] 时，利用 next 数组跳转
while (j > 0 && s[i] != p[j]) {
j = nxt[j - 1];
}
// 如果 s[i] == p[j]，模式串指针前移
if (s[i] == p[j]) {
j++;
}
// 模式串完全匹配
if (j == m) {
// 匹配位置 = 当前文本串位置 - 模式串长度 + 1
matches.push_back(i - m + 1);
// 继续搜索下一个匹配：利用 next 数组跳转
j = nxt[j - 1];
}
}
return matches;
}
int main() {
string text, pattern;
cin >> text >> pattern;
vector<int> matches = kmpSearch(text, pattern);
// 输出所有匹配位置（下标从 0 开始）
for (int pos : matches) {
cout << pos << endl;
}
// 输出 next 数组
cout << "next数组: ";
for (int i = 0; i < (int)pattern.size(); i++) {
cout << nxt[i] << " ";
}
cout << endl;
return 0;
}
复杂度分析：
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 构建 next 数组 | O(m) | O(m) | 模式串长度为 m |
| KMP 匹配 | O(n) | O(1) | 文本串长度为 n |
| 总计 | O(n + m) | O(m) | 线性时间复杂度 |
KMP 的核心思想
KMP 的精髓在于：当发生失配时，我们已经知道文本串中的一段字符（它们与模式串的某个前缀匹配）。利用 next 数组，我们可以直接跳过这段已知信息，将模式串滑动到正确的位置继续比较。这就是"不回退文本串指针"的含义——文本串的每个字符最多被访问两次（一次匹配，一次失配后的跳转），因此总时间为 \(O(n)\)。
next 数组的常见应用
- 字符串匹配：找所有匹配位置
- 求最小循环节：字符串 \(s\) 的最小循环节长度为 \(n - \pi[n-1]\)（当 \(n \bmod (n - \pi[n-1]) == 0\) 时）
- 求最长公共前后缀：直接查 \(\pi[n-1]\)
- 统计前缀出现次数：利用 next 数组链式跳转
13.3 Trie（字典树）¶
13.3.1 基本概念¶
Trie（发音同 "try"），又称字典树或前缀树，是一种树形数据结构，用于高效存储和检索字符串集合。Trie 的每个节点代表一个字符，从根到某个节点的路径构成一个字符串的前缀。
核心性质：
- 根节点不存储字符
- 每条边代表一个字符
- 从根到任意节点的路径构成一个前缀
- 使用公共前缀来节省存储空间
graph TD
subgraph Trie 示例 - 存储 "abc", "abd", "acd", "b"
R["根节点"] --> A["a"]
R --> B["b (标记: 单词结束)"]
A --> AB["b"]
A --> AC["c"]
AB --> ABA["c (标记: 单词 'abc' 结束)"]
AB --> ABB["d (标记: 单词 'abd' 结束)"]
AC --> ACA["d (标记: 单词 'acd' 结束)"]
end13.3.2 数组实现 Trie¶
在 ACM 竞赛中，通常使用数组模拟实现 Trie，以获得更高的效率。每个节点用一个数组 son[node][c] 存储指向字符 c 对应子节点的指针。
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100010; // 最大节点数（所有字符串的总字符数）
const int CHARSET = 26; // 字符集大小（小写字母 26 个）
int son[MAXN][CHARSET]; // son[i][c]: 节点 i 的字符 c 子节点
int cnt[MAXN]; // cnt[i]: 以节点 i 结尾的单词数量
int idx; // 当前已分配的节点数（0 号节点为根）
// 初始化 Trie
void init() {
memset(son, 0, sizeof son);
memset(cnt, 0, sizeof cnt);
idx = 0;
}
// 插入字符串 s
// 时间复杂度: O(L)，L 为字符串长度
void insert(const string& s) {
int p = 0; // 从根节点出发
for (char ch : s) {
int c = ch - 'a'; // 将字符映射到 0~25
// 如果对应子节点不存在，创建新节点
if (!son[p][c]) {
son[p][c] = ++idx;
}
p = son[p][c]; // 移动到子节点
}
cnt[p]++; // 标记该节点为一个单词的结尾
}
// 查找字符串 s 是否存在
// 返回: s 在 Trie 中出现的次数
// 时间复杂度: O(L)
int search(const string& s) {
int p = 0; // 从根节点出发
for (char ch : s) {
int c = ch - 'a';
if (!son[p][c]) {
return 0; // 路径不存在，说明 s 不在 Trie 中
}
p = son[p][c];
}
return cnt[p]; // 返回该单词的出现次数
}
// 查询是否有以 prefix 为前缀的字符串
// 返回: Trie 中以 prefix 为前缀的字符串数量
// 时间复杂度: O(L)
int startsWith(const string& prefix) {
int p = 0;
for (char ch : prefix) {
int c = ch - 'a';
if (!son[p][c]) {
return 0; // 前缀路径不存在
}
p = son[p][c];
}
// 需要遍历该子树来统计数量（此处简化为返回 1 表示前缀存在）
return 1;
}
int main() {
init();
// 插入字符串
insert("apple");
insert("app");
insert("application");
// 查找
cout << "search('app'): " << search("app") << endl; // 输出 1
cout << "search('apple'): " << search("apple") << endl; // 输出 1
cout << "search('ap'): " << search("ap") << endl; // 输出 0（不是完整单词）
cout << "startsWith('app'): " << startsWith("app") << endl; // 输出 1
return 0;
}
复杂度分析：
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 插入 | O(L) | O(L) | L 为单个字符串长度 |
| 查找 | O(L) | O(1) | 沿路径走一遍 |
| 前缀查询 | O(L) | O(1) | 沿前缀路径走一遍 |
| 总空间 | - | O(N * L * C) | N 个字符串，字符集大小 C |
Trie 的常见应用
- 自动补全/词频统计：在搜索引擎中用于前缀匹配和排序
- XOR 最大值：将整数的二进制位存入 Trie，可以快速查询与给定整数 XOR 结果最大的值
- 拼写检查：检查单词是否存在或给出最相近的建议
- 01-Trie：字符集为 {0, 1} 的特殊 Trie，常用于处理二进制异或问题
- AC 自动机：将多个模式串建成 Trie，结合 KMP 的 fail 指针实现多模式匹配（见 13.4 节）
Trie 的空间开销
数组实现的 Trie 空间开销较大（每个节点需要一个大小为字符集的数组）。如果字符集很大（如 Unicode），需要考虑使用 unordered_map 替代数组来存储子节点，或者使用链表实现。在竞赛中，通常只处理小写字母或数字，数组实现是最高效的。
13.4 AC 自动机¶
13.4.1 问题引入¶
多模式串匹配问题：给定 \(n\) 个模式串 \(s_1, s_2, \ldots, s_n\) 和一个文本串 \(t\)，统计有多少个模式串在文本串中出现过。
如果对每个模式串单独跑一遍 KMP，总时间为 \(O(n \cdot |t| + \sum |s_i|)\)——文本串会被反复扫描 \(n\) 遍，当模式串数量很大（如 \(10^5\) 个）时完全无法承受。
AC 自动机（Aho-Corasick Automaton）解决了这个问题：先把所有模式串插入一棵 Trie（13.3 节），再借鉴 KMP 的失配思想在 Trie 上构建 fail 指针，文本串只需在自动机上走一遍，就能同时完成对所有模式串的匹配。可以概括为一个公式：
13.4.2 fail 指针与 Trie 图¶
定义：设节点 \(u\) 代表"从根走到 \(u\)"形成的字符串，则 \(fail[u]\) 指向 \(u\) 所代表字符串的最长真后缀在 Trie 中对应的节点（若不存在这样的后缀，则指向根）。
这与 KMP 的 next 数组"最长的既是真前缀又是真后缀"的思想一致：当匹配走不下去时，跳到 \(fail[u]\) 相当于保留当前已匹配串的最长可用后缀，接着尝试。
以模式串集合 {he, she, his, hers} 为例（实线为 Trie 树边，虚线为 fail 指针，指向根的省略）：
graph TD
subgraph Trie 与 fail 指针 - 模式串 he / she / his / hers
R["根"] --> H["h"]
R --> S["s"]
H --> HE["he (结尾)"]
H --> HI["hi"]
HI --> HIS["his (结尾)"]
HE --> HER["her"]
HER --> HERS["hers (结尾)"]
S --> SH["sh"]
SH --> SHE["she (结尾)"]
SH -.->|fail| H
SHE -.->|fail| HE
HIS -.->|fail| S
HERS -.->|fail| S
end例如节点 "she" 的最长真后缀中能在 Trie 中找到的是 "he"，故 \(fail[\text{she}] = \text{he}\)——文本走到 "she" 时，模式串 "he" 也恰好在此结束出现。
fail 指针用 BFS 逐层构建（保证处理节点 \(v\) 时，深度比它小的节点的 fail 都已求出）：
- 深度为 1 的节点：fail 一律指向根。
- 若子节点 \(v = tr[u][c]\) 存在：\(fail[v] = tr[fail[u]][c]\)。
- 若 \(tr[u][c]\) 不存在：直接令 \(tr[u][c] = tr[fail[u]][c]\)。
第 3 步把 Trie 补成了 Trie 图：任何节点对任何字符都有转移，匹配时永不"失配"，不需要像 KMP 那样在循环里反复回跳，每读一个字符只走一步。
13.4.3 文本匹配¶
文本串在 Trie 图上逐字符转移（每步 \(O(1)\)）。走到节点 \(p\) 时，\(p\) 的 fail 链上的每个"结尾节点"都对应一个恰好在当前位置结束出现的模式串，因此沿 fail 链上溯统计即可。为避免重复统计（同时保证复杂度），统计过的节点将计数置为 \(-1\)，之后再遇到就直接停止上溯。
13.4.4 完整模板与例题（洛谷 P3808）¶
题意：给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\)，求有多少个模式串在文本串中出现过（相同的模式串分别计数）。\(1 \le n \le 10^6\)，\(\sum |s_i| \le 10^6\)，\(|t| \le 10^6\)。
#include <iostream>
#include <string>
#include <queue>
using namespace std;
const int MAXN = 1000010; // Trie 节点数上限（所有模式串的总长度）
const int CHARSET = 26; // 字符集大小（小写字母）
// 注意：tr 数组约 100MB 级别（1e6 x 26 x 4 字节），必须定义为全局变量，
// 局部定义会爆栈；若题目空间较紧，可按 ∑|s_i| 的实际上限缩小 MAXN
int tr[MAXN][CHARSET]; // tr[u][c]: 节点 u 的字符 c 出边（建好 fail 后为 Trie 图）
int fail[MAXN]; // fail[u]: 节点 u 的失配指针
int cnt[MAXN]; // cnt[u]: 以节点 u 结尾的模式串个数
int idx; // 已分配的节点数（0 号节点为根）
// 第一步：把模式串插入 Trie（与 13.3 节完全相同）
void insert(const string& s) {
int p = 0;
for (char ch : s) {
int c = ch - 'a';
if (!tr[p][c]) tr[p][c] = ++idx;
p = tr[p][c];
}
cnt[p]++; // 该节点是一个模式串的结尾
}
// 第二步：BFS 逐层构建 fail 指针，同时把 Trie 补成 Trie 图
void build() {
queue<int> q;
// 深度为 1 的节点：fail 一律指向根（初值 0，无需显式赋值）
for (int c = 0; c < CHARSET; c++) {
if (tr[0][c]) q.push(tr[0][c]);
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int c = 0; c < CHARSET; c++) {
int v = tr[u][c];
if (v) {
// 子节点存在：其 fail = 父节点 fail 沿字符 c 的转移
fail[v] = tr[fail[u]][c];
q.push(v);
} else {
// 子节点不存在：出边直接指向 fail 的对应转移（补成 Trie 图）
tr[u][c] = tr[fail[u]][c];
}
}
}
}
// 第三步：文本串在 Trie 图上跑一遍，沿 fail 链统计出现的模式串
int query(const string& t) {
int p = 0, res = 0;
for (char ch : t) {
p = tr[p][ch - 'a']; // Trie 图上转移，永不失配
// 沿 fail 链上溯：链上每个结尾节点对应一个在此处出现的模式串
// 统计过的节点置为 -1，保证每个节点只被统计一次
for (int u = p; u && cnt[u] != -1; u = fail[u]) {
res += cnt[u];
cnt[u] = -1;
}
}
return res;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
string s;
for (int i = 0; i < n; i++) {
cin >> s;
insert(s);
}
build();
string t;
cin >> t;
cout << query(t) << endl;
return 0;
}
验证：洛谷 P3808 样例（模式串 a、aa、aa，文本 ab）输出 1；经典用例——模式串 {he, she, his, hers} 匹配文本 "ahishers"，he、she、his、hers 各出现一次，输出 4。
13.4.5 复杂度分析¶
设 \(L = \sum |s_i|\) 为模式串总长，\(m = |t|\) 为文本串长，\(C\) 为字符集大小（此处为 26，视作常数）：
| 阶段 | 时间复杂度 | 说明 |
|---|---|---|
| 建 Trie | O(L) | 逐字符插入 |
| 建 fail（含 Trie 图） | O(L * C) | BFS 中每个节点枚举整个字符集 |
| 文本匹配 | O(m + L) 均摊 | Trie 图转移每字符 O(1)；置 -1 保证每个节点的计数只被统计一次 |
| 总计 | O(L + m) | 即 O(∑模式串长 + 文本串长)，字符集视为常数 |
| 指标 | 空间复杂度 | 说明 |
|---|---|---|
| tr 数组 | O(L * C) | 空间瓶颈，注意按题目范围开数组 |
| fail / cnt 数组 | O(L) | 一维数组 |
为什么匹配是均摊线性的
匹配中每读一个字符，Trie 图上的转移只走一步，这部分严格 \(O(m)\)。沿 fail 链上溯看似可能很长，但每个节点被完整统计一次后就置为 \(-1\)，之后任何上溯一碰到 \(-1\) 节点立即停止——所以所有上溯的总步数不超过节点数 \(O(L)\)。两部分合计 \(O(m + L)\)。如果不做标记而每次都暴力跳完整条 fail 链，最坏会退化到 \(O(m \cdot L)\)（例如全 'a' 的数据）。
AC 自动机的常见坑
- 数组大小：
MAXN必须按所有模式串的总长度开，不是单个串的长度；tr数组是空间瓶颈，本模板约 100MB，需按题目实际范围调整。 - 必须置 -1（或改用 fail 树）：沿 fail 链统计时不做标记，复杂度会退化（见上方 note）。需要统计每个模式串出现次数（如洛谷 P5357 二次加强版）时，不能置 -1，应改为在 fail 树上求子树和。
- build 之后 Trie 已被改写：第 3 步把不存在的出边补成了转移边，
tr不再是原始 Trie，如需原树结构要提前备份。 - 多组数据要完整清空：
tr、fail、cnt、idx都要重置，只清idx会残留脏边。 - 大数组定义为全局：与 13.1 节的哈希数组同理，放在函数内会爆栈。
13.5 Manacher 算法¶
13.5.1 问题定义¶
最长回文子串问题：给定一个字符串，找出其中最长的回文子串的长度。
例如，字符串 "abacaba" 的最长回文子串是 "abacaba"（长度 7），而 "abcba" 的最长回文子串是 "abcba"（长度 5）。
朴素算法对每个中心向两边扩展，时间复杂度为 \(O(n^2)\)。Manacher 算法可以在 \(O(n)\) 时间内解决这个问题。
13.5.2 字符串预处理¶
为了统一处理奇数长度和偶数长度的回文串，我们对原字符串进行预处理：在每两个相邻字符之间插入一个特殊字符（如 #），并在首尾分别添加特殊字符（如 ^ 和 $）。
例如：
- 原串 "abc" -> 预处理后 "^#a#b#c#$"
- 原串 "abba" -> 预处理后 "^#a#b#b#a#$"
这样，所有回文串的中心一定落在某个字符上（不再是两个字符之间的间隙），统一了处理逻辑。
graph LR
subgraph 预处理示意
A["原串: abc"] --> B["预处理: ^#a#b#c#$"]
C["原串: abba"] --> D["预处理: ^#a#b#b#a#$"]
end13.5.3 核心变量¶
- p[i]：以位置 \(i\) 为中心的回文半径（包含中心字符本身）。即预处理后字符串中，以 \(i\) 为中心的最长回文子串长度为 \(2 \cdot p[i] - 1\)
- center：当前已知回文串能够到达最右端的那个回文串的中心
- right：当前已知回文串的最右端位置（不包含该位置）
13.5.4 核心思想¶
当计算 p[i] 时，如果 i 在当前 right 范围内，我们可以利用已有的回文信息，将 p[i] 初始化为 p[i 关于 center 的对称点] 的值，从而跳过一部分比较。
具体来说，设 \(i\) 关于 \(center\) 的对称点为 \(i' = 2 \cdot center - i\)：
- 如果 \(i < right\)，则 \(p[i] \geq \min(p[i'], right - i)\)
- 然后在此基础上继续向外扩展
- 每次扩展成功都会更新 right，而 right 只会增加不会减少，因此总时间复杂度为 \(O(n)\)
13.5.5 完整代码实现¶
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int MAXN = 2000010; // 预处理后字符串最大长度
int p[MAXN]; // p[i]: 以位置 i 为中心的回文半径
// Manacher 算法
// s: 原始字符串
// 返回: 最长回文子串的长度
// 时间复杂度: O(n)
int manacher(const string& s) {
// 步骤 1: 预处理，在每两个字符间插入 '#'
string t = "^#";
for (char ch : s) {
t += ch;
t += '#';
}
t += '$'; // 首尾添加哨兵字符，防止越界
int n = t.size();
int center = 0, right = 0; // 当前回文串的中心和右边界
int maxLen = 0; // 最长回文半径
// 步骤 2: 遍历预处理后的字符串
for (int i = 1; i < n - 1; i++) {
// 利用对称性初始化 p[i]
if (i < right) {
// i' = 2 * center - i 是 i 关于 center 的对称点
p[i] = min(p[2 * center - i], right - i);
} else {
p[i] = 1; // 初始半径为 1（只包含中心字符本身）
}
// 步骤 3: 以 i 为中心，尝试向两边扩展
while (t[i - p[i]] == t[i + p[i]]) {
p[i]++;
}
// 步骤 4: 更新 center 和 right
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
// 更新最大回文半径
maxLen = max(maxLen, p[i]);
}
// 最长回文子串的原串长度 = 回文半径 - 1
// 因为预处理后半径为 R 的回文串，对应原串长度为 R - 1
return maxLen - 1;
}
int main() {
string s;
cin >> s;
cout << manacher(s) << endl;
return 0;
}
13.5.6 详解示例¶
以字符串 "ababa" 为例：
预处理后：^#a#b#a#b#a#$
| 下标 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| t[i] | ^ | # | a | # | b | # | a | # | b | # | a | $ |
| p[i] | 0 | 1 | 2 | 1 | 4 | 1 | 6 | 1 | 4 | 1 | 2 | 0 |
当 \(i = 6\)（字符 'a'，正中心）时，\(p[6] = 6\)，对应原串回文长度为 \(6 - 1 = 5\)，即 "ababa"。
复杂度分析：
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | right 只增不减，每个位置最多被访问常数次 |
| 空间复杂度 | O(n) | 存储预处理后的字符串和 p 数组 |
| 预处理 | O(n) | 插入分隔符 |
Manacher 算法的边界条件
- 预处理时必须添加哨兵字符（如
^和$），否则扩展时可能越界 - 原始字符串长度为 \(n\) 时，预处理后长度为 \(2n + 3\)，数组需要开足够大
- 最终结果需要将预处理字符串中的回文半径减 1，才能得到原串的回文长度
- 如果需要输出回文子串本身（而不仅仅是长度），需要记录 maxLen 对应的中心位置，然后根据公式还原
13.6 Z 函数简介¶
13.6.1 定义¶
给定长度为 \(n\) 的字符串 \(s\)，Z 函数定义为：\(z[i]\) 表示 \(s\) 与 \(s[i..n-1]\) 的最长公共前缀（LCP）的长度。
按照惯例，\(z[0] = 0\)（或有时定义为 \(n\)，取决于实现）。
示例：对于字符串 "aabxaab"：
| 下标 i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| 字符 | a | a | b | x | a | a | b |
| z[i] | 0 | 1 | 0 | 0 | 3 | 1 | 0 |
- \(z[1] = 1\)：$s[1..] = $ "abxaab"，与 $s = $ "aabxaab" 的最长公共前缀是 "a"，长度 1
- \(z[4] = 3\)：$s[4..] = $ "aab"，与 $s = $ "aabxaab" 的最长公共前缀是 "aab"，长度 3
13.6.2 Z 函数的构建¶
Z 函数的构建过程与 KMP 的 next 数组类似，也利用了"已计算的信息"来加速。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
// 构建 Z 函数
// s: 输入字符串
// 返回: z 数组
// 时间复杂度: O(n)
vector<int> zFunction(const string& s) {
int n = s.size();
vector<int> z(n, 0);
// l, r 维护当前已知的最右端的 Z-box
// Z-box: 某个 z[i] 对应的 s[0..z[i]-1] == s[i..i+z[i]-1] 的区间
for (int i = 1, l = 0, r = 0; i < n; i++) {
// 利用已知的 Z-box 信息初始化 z[i]
if (i <= r) {
z[i] = min(r - i + 1, z[i - l]);
}
// 暴力扩展
while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
z[i]++;
}
// 更新 Z-box
if (i + z[i] - 1 > r) {
l = i;
r = i + z[i] - 1;
}
}
return z;
}
int main() {
string s;
cin >> s;
vector<int> z = zFunction(s);
for (int i = 0; i < (int)z.size(); i++) {
cout << "z[" << i << "] = " << z[i] << endl;
}
return 0;
}
13.6.3 Z 函数用于模式匹配¶
Z 函数的一个经典应用是模式匹配：将模式串 \(p\) 和文本串 \(t\) 拼接为 \(s = p + "\$" + t\)（\(\$\) 是一个不在两个串中出现的分隔符），然后计算 \(s\) 的 Z 函数。对于 \(t\) 中的每个位置，如果对应的 \(z\) 值等于 \(|p|\)，则说明找到了一个匹配。
// 利用 Z 函数进行模式匹配
// pattern: 模式串
// text: 文本串
// 返回: 所有匹配的起始位置
vector<int> zMatch(const string& pattern, const string& text) {
string s = pattern + "$" + text;
vector<int> z = zFunction(s);
int m = pattern.size();
vector<int> matches;
// 遍历文本串对应的部分
for (int i = m + 1; i < (int)s.size(); i++) {
if (z[i] == m) {
matches.push_back(i - m - 1); // 转换为 text 中的下标
}
}
return matches;
}
复杂度分析：
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 构建 Z 函数 | O(n) | O(n) |
| Z 函数模式匹配 | O(n + m) | O(n + m) |
Z 函数与 next 数组的关系
Z 函数和 KMP 的 next 数组（前缀函数）都是线性时间构建的字符串自匹配工具。两者的适用场景略有不同： - next 数组：更自然地用于 KMP 匹配算法 - Z 函数：更直观地用于"子串是否等于某个前缀"这类查询，以及某些数学性质的推导 - 两者可以在线性时间内互相转换
13.7 后缀数组简介¶
13.7.1 定义¶
后缀数组（Suffix Array, SA）是字符串处理中非常强大的工具。给定一个长度为 \(n\) 的字符串 \(s\)，其后缀数组 \(SA\) 定义如下：
- \(SA[i]\) 表示将 \(s\) 的所有后缀按字典序排序后，第 \(i\) 小的后缀的起始下标
例如，字符串 "banana" 的所有后缀：
| 排名 i | SA[i] | 后缀 |
|---|---|---|
| 0 | 5 | a |
| 1 | 3 | ana |
| 2 | 1 | anana |
| 3 | 0 | banana |
| 4 | 4 | na |
| 5 | 2 | nana |
13.7.2 倍增算法（O(n log^2 n)）¶
最常用的后缀数组构建算法是倍增法。核心思想：
- 首先按每个后缀的第一个字符排序
- 然后按前 2 个字符排序（利用前 1 个字符的排序结果）
- 再按前 4 个字符排序...
- 每次将排序的长度翻倍，直到长度 >= n
每次排序可以用基数排序（O(n)），共需 \(O(\log n)\) 轮，总时间复杂度为 \(O(n \log n)\) 或 \(O(n \log^2 n)\)（取决于排序方法）。
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 1000010;
int sa[MAXN]; // 后缀数组: sa[i] = 第 i 小后缀的起始下标
int rk[MAXN]; // 排名数组: rk[i] = 后缀 i 的排名
int tmp[MAXN]; // 辅助数组
int cnt[MAXN]; // 基数排序的计数数组
// 使用基数排序的后缀数组构建（简化版本，O(n log^2 n)）
// s: 输入字符串（下标从 0 开始）
// n: 字符串长度
void buildSA(string& s, int n) {
// 初始按单个字符排序
for (int i = 0; i < n; i++) {
sa[i] = i;
rk[i] = s[i];
}
// 倍增过程：k 为当前排序的子串长度
for (int k = 1; k < n; k <<= 1) {
// 按第二关键字排序：即按 sa[i] - k 位置的排名排序
// 第二关键字为 0 的排在前面（即起始位置 < k 的后缀）
auto cmp = [&](int a, int b) {
if (rk[a] != rk[b]) return rk[a] < rk[b];
int ra = (a + k < n) ? rk[a + k] : -1;
int rb = (b + k < n) ? rk[b + k] : -1;
return ra < rb;
};
sort(sa, sa + n, cmp);
// 更新排名
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
for (int i = 0; i < n; i++) {
rk[i] = tmp[i];
}
// 如果所有排名已经唯一，提前退出
if (rk[sa[n - 1]] == n - 1) break;
}
}
int main() {
string s;
cin >> s;
int n = s.size();
buildSA(s, n);
// 输出后缀数组
cout << "后缀数组: ";
for (int i = 0; i < n; i++) {
cout << sa[i] << " ";
}
cout << endl;
return 0;
}
13.7.3 height 数组与 LCP¶
height 数组定义：\(height[i] = \text{LCP}(s[SA[i-1]..], s[SA[i]..])\)，即排名第 \(i\) 的后缀与排名第 \(i-1\) 的后缀的最长公共前缀长度。
height 数组有一个非常重要的性质（性质 LCP）：对于任意 \(i < j\)，\(\text{LCP}(SA[i], SA[j]) = \min(height[i+1], height[i+2], \ldots, height[j])\)。
这意味着，height 数组可以将子串间的 LCP 问题转化为区间最小值问题。
// 构建 height 数组
// s: 输入字符串, sa: 后缀数组, rk: 排名数组
// n: 字符串长度
// 时间复杂度: O(n)
int height[MAXN];
void buildHeight(const string& s, int n) {
for (int i = 0, k = 0; i < n; i++) {
if (rk[i] == 0) {
height[0] = 0;
continue;
}
// 利用性质: height[rk[i]] >= height[rk[i-1]] - 1
if (k > 0) k--;
int j = sa[rk[i] - 1]; // 排名在 i 前一位的后缀起始位置
while (i + k < n && j + k < n && s[i + k] == s[j + k]) {
k++;
}
height[rk[i]] = k;
}
}
13.7.4 常见应用¶
应用一：最长重复子串
最长重复子串的长度就是 height 数组中的最大值。
应用二：不同子串的个数
一个长度为 \(n\) 的字符串的不同子串总数为：
因为每对相邻后缀共享 height[i] 个前缀，这些前缀对应的子串是重复的。
| 应用 | 时间复杂度 | 说明 |
|---|---|---|
| 构建后缀数组 | O(n log^2 n) | 倍增法（使用 sort） |
| 构建后缀数组 | O(n log n) | 倍增法（使用基数排序） |
| 构建 height 数组 | O(n) | 利用性质 LCP |
| 最长重复子串 | O(n) | height 数组最大值 |
| 不同子串个数 | O(n) | 利用 height 数组公式 |
| 两子串 LCP | O(1) | 配合 ST 表求区间最小值 |
关于更高效的构建算法
后缀数组的倍增法实现简单、常数小，足以应对绝大多数竞赛题目。如果需要 \(O(n)\) 的构建时间，可以学习 SA-IS 算法（Suffix Array by Induced Sorting），该算法通过分类后缀和诱导排序，在线性时间内构建后缀数组。不过 SA-IS 的实现较为复杂，在竞赛中一般不需要。另外，后缀自动机（SAM）和后缀树是更强大的字符串处理工具，适合处理更复杂的字符串问题，属于进阶内容。
13.8 算法对比与总结¶
在结束本章之前，我们将各算法的适用场景进行对比总结：
graph TD
subgraph 字符串算法选择指南
A{"需要解决什么问题?"}
A -->|"子串快速比较/哈希"| B["字符串哈希"]
A -->|"单模式串匹配"| C["KMP 算法"]
A -->|"前缀查询/词典"| D["Trie 字典树"]
A -->|"最长回文子串"| E["Manacher 算法"]
A -->|"后缀相关问题"| F["后缀数组 / Z 函数"]
A -->|"多模式串匹配"| G["AC 自动机"]
end| 算法 | 适用场景 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|
| 字符串哈希 | 子串比较、子串出现次数、回文判断 | 预处理 O(n)，查询 O(1) | O(n) |
| KMP | 单模式串匹配、最小循环节 | O(n + m) | O(m) |
| Trie | 前缀查询、词典存储、XOR 最大值 | O(L) 每次操作 | O(N * L * C) |
| AC 自动机 | 多模式串匹配、模式串出现统计 | O(L + m)，L 为模式串总长，m 为文本长 | O(L * C) |
| Manacher | 最长回文子串、回文计数 | O(n) | O(n) |
| Z 函数 | 模式匹配、子串与前缀关系 | O(n) | O(n) |
| 后缀数组 | 子串排序、LCP、不同子串计数 | O(n log n) | O(n) |
ACM Day10 字符串 练习题¶
| 题号 | 平台 | 题目 | 难度 | 链接 | 完成 |
|---|---|---|---|---|---|
| 1948D | CF | Tandem Repeats? | 1700 | https://codeforces.com/contest/1948/problem/D | - [ ] |
| 2010C2 | CF | Message Transmission Error (hard version) | 1700 | https://codeforces.com/contest/2010/problem/C2 | - [ ] |
| 1979D | CF | Fixing a Binary String | 1800 | https://codeforces.com/contest/1979/problem/D | - [ ] |
| 2069D | CF | Palindrome Shuffle | 1800 | https://codeforces.com/contest/2069/problem/D | - [ ] |
| 1968G1 | CF | Division + LCP (easy version) | 1900 | https://codeforces.com/contest/1968/problem/G1 | - [ ] |
| 1902E | CF | Collapsing Strings | 1900 | https://codeforces.com/contest/1902/problem/E | - [ ] |
| 1943B | CF | Non-Palindromic Substring | 2000 | https://codeforces.com/contest/1943/problem/B | - [ ] |
| 1984D | CF | "a" String Problem | 2000 | https://codeforces.com/contest/1984/problem/D | - [ ] |
| abc346_f | AT | String Shifting | 1900 | https://atcoder.jp/contests/abc346/tasks/abc346_f | - [ ] |
| abc284_f | AT | Yet Another String Game | 1800 | https://atcoder.jp/contests/abc284/tasks/abc284_f | - [ ] |
| abc287_f | AT | Predilection | 1800 | https://atcoder.jp/contests/abc287/tasks/abc287_f | - [ ] |
| P3375 | 洛谷 | 【模板】KMP字符串匹配 | 1700 | https://www.luogu.com.cn/problem/P3375 | - [ ] |
| P3501 | 洛谷 | [POI2010] ANT-Antisymmetry | 1900 | https://www.luogu.com.cn/problem/P3501 | - [ ] |
| P2852 | 洛谷 | [USACO06DEC] Milk Patterns G | 1800 | https://www.luogu.com.cn/problem/P2852 | - [ ] |