第 9 章字符串算法#

本章目标：掌握从暴力匹配到 KMP、Trie、字符串哈希、Manacher 和 AC 自动机的基本思想。

9.1 学习目标#

理解字符串匹配的核心问题。
掌握 KMP 前缀函数。
掌握 Trie 的插入和查询。
掌握字符串哈希的前缀形式。
了解 Manacher 和 AC 自动机适用场景。

9.2 字符串匹配问题#

给定文本 T 和模式 P，找 P 在 T 中出现的位置。

暴力匹配复杂度：

O(|T|\cdot |P|)

KMP 可以优化到：

O(|T|+|P|)

9.3 KMP 与前缀函数#

前缀函数 $\pi[i]$ 表示字符串 $s[0..i]$ 的最长相等真前后缀长度。

例如：

1
s = ababa
2
pi = 0 0 1 2 3

计算过程：

1
vector<int> prefix_function(string s) {
2
    int n = s.size();
3
    vector<int> pi(n);
4
    for (int i = 1; i < n; i++) {
5
        int j = pi[i - 1];
6
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
7
        if (s[i] == s[j]) j++;
8
        pi[i] = j;
9
    }
10
    return pi;
11
}

失配时跳到 $\pi[j-1]$ ，因为这个长度仍可能继续匹配。

9.4 Trie 字典树#

Trie 用路径表示字符串。

适用场景：

前缀查询。
字典集合。
单词自动补全。
最大异或对。

插入：

1
void insert(string s) {
2
    int u = 0;
3
    for (char c : s) {
4
        int x = c - 'a';
5
        if (!tr[u][x]) tr[u][x] = ++idx;
6
        u = tr[u][x];
7
    }
8
    end[u]++;
9
}

空间复杂度约为所有字符串长度总和乘字符集大小。

9.5 字符串哈希#

多项式哈希：

H(s)=\sum_{i=0}^{n-1} val(s_i) p^i \bmod M

更常用前缀写法：

h[i+1]=h[i]\cdot p + val(s_i)

子串 $[l,r)$ 哈希：

H(l,r)=h[r]-h[l]\cdot p^{r-l}

哈希可用于：

子串比较。
最长重复子串。
回文判断。
字符串去重。

9.6 Manacher#

Manacher 在线性时间求每个中心的最长回文半径。

核心技巧：

在字符间插入特殊符号，统一奇偶回文。
维护当前最右回文区间。
利用对称位置的半径减少重复扩展。

复杂度： $O(n)$ 。

9.7 AC 自动机#

AC 自动机用于多模式串匹配。它把 Trie 和 KMP 的 fail 指针结合起来。

用途：

敏感词匹配。
多关键词检索。
字符串 DP。

构建思路：

把所有模式串插入 Trie。
BFS 建立 fail 指针。
扫描文本时按自动机转移。

9.8 易错点#

KMP 中 j 回退写成 j—，退化成暴力。
Trie 节点数组没初始化。
哈希取模后出现负数。
单哈希碰撞导致误判。
Manacher 插入分隔符后下标换算错误。
AC 自动机 fail 指针没有 BFS 构建。

9.9 练习#

用 KMP 找模式串所有出现位置。
用 Trie 实现单词插入和前缀查询。
用字符串哈希判断两个子串是否相等。
用 Manacher 求最长回文子串。
用 AC 自动机统计多个模式串出现次数。

ACM/OI 扩展：ACM 字符串模板补充#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. KMP 模板#

前缀函数是最常用的 KMP 写法。

1
vector<int> prefix_function(const string& s) {
2
    int n = (int)s.size();
3
    vector<int> pi(n);
4
    for (int i = 1; i < n; ++i) {
5
        int j = pi[i - 1];
6
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
7
        if (s[i] == s[j]) ++j;
8
        pi[i] = j;
9
    }
10
    return pi;
11
}

要点：

匹配可对 pattern + # + text 求前缀函数。
# 必须是不在字符集中的分隔符。

2. Z 函数#

Z[i] 表示 s[i..] 与 s 的最长公共前缀长度。

1
vector<int> z_function(const string& s) {
2
    int n = s.size();
3
    vector<int> z(n);
4
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
5
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
6
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i];
7
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
8
    }
9
    return z;
10
}

要点：

Z 函数也能做模式匹配。
比 KMP 在某些前缀匹配统计中更直观。

3. 双哈希#

降低字符串哈希碰撞概率。

1
const long long mod1 = 1000000007, mod2 = 1000000009, base = 911382323;
2
struct H { long long x, y; };
3
bool operator==(const H& a, const H& b) { return a.x == b.x && a.y == b.y; }

要点：

base 可随机选择。
自然溢出 unsigned long long 也常用。

4. 后缀数组用途#

后缀数组按字典序排列所有后缀，LCP 表示相邻后缀最长公共前缀。

要点：

不同子串数量： $n(n+1)/2 - \sum LCP$ 。
最长重复子串：max LCP。
多个串公共子串：拼接后结合来源和 LCP。

5. AC 自动机应用#

多模式匹配和敏感词过滤常用。

要点：

Trie 边表示字符转移。
fail 指针表示当前匹配失败后最长可用后缀。
BFS 建 fail。
扫描文本时按自动机转移并累计终止标记。

训练题型：

多模式串出现次数。
禁止模式串的字符串计数 DP。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

字符串进阶补充#

Manacher 模板#

线性时间求所有回文半径。

1
vector<int> manacher(string s) {
2
    string t = "#";
3
    for (char c : s) t += c, t += '#';
4
    int n = t.size(), center = 0, right = 0;
5
    vector<int> p(n);
6
    for (int i = 0; i < n; ++i) {
7
        int mir = 2 * center - i;
8
        if (i < right) p[i] = min(right - i, p[mir]);
9
        while (i - p[i] - 1 >= 0 && i + p[i] + 1 < n && t[i-p[i]-1] == t[i+p[i]+1]) ++p[i];
10
        if (i + p[i] > right) center = i, right = i + p[i];
11
    }
12
    return p;
13
}

插入 # 后统一奇偶。
原串回文长度与 p 数组需要换算。

最小表示法#

求循环同构字符串的字典序最小旋转。

双指针 i、j 比较两个候选起点。
失配后跳过不可能成为最优的区间。
复杂度 $O(n)$ 。

后缀自动机 SAM#

SAM 表示一个字符串所有子串的自动机。

不同子串数量： $\sum (len[v]-len[link[v]])$ 。
可求每个子串出现次数。
适合在线扩展。

回文自动机 PAM#

维护所有不同回文子串。

两个根：长度 -1 和 0。
每加入一个字符，最多新增一个回文节点。
适合回文计数和回文 DP。

字符串题选型#

先判断是单模式、多模式、回文、子串排序还是动态维护。

单模式：KMP/Z。
多模式：AC 自动机。
回文：Manacher/PAM。
子串排名：SA/SAM。
动态字典：Trie。

高频模板训练卡#

这一组训练卡用于把“09_字符串算法”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：KMP#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 KMP。
优先模板：使用 KMP 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 KMP 解决一道模板题并解释每个数组含义。

卡 2：Z 函数#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 Z 函数。
优先模板：使用 Z 函数模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 Z 函数解决一道模板题并解释每个数组含义。

卡 3：Trie#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 Trie。
优先模板：使用 Trie 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 Trie 解决一道模板题并解释每个数组含义。

卡 4：01 Trie#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 01 Trie。
优先模板：使用 01 Trie 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 01 Trie 解决一道模板题并解释每个数组含义。

卡 5：字符串哈希#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或字符串哈希。
优先模板：使用字符串哈希模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用字符串哈希解决一道模板题并解释每个数组含义。

卡 6：双哈希#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或双哈希。
优先模板：使用双哈希模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用双哈希解决一道模板题并解释每个数组含义。

卡 7：Manacher#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 Manacher。
优先模板：使用 Manacher 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 Manacher 解决一道模板题并解释每个数组含义。

卡 8：AC 自动机#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 AC 自动机。
优先模板：使用 AC 自动机模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 AC 自动机解决一道模板题并解释每个数组含义。

卡 9：后缀数组#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或后缀数组。
优先模板：使用后缀数组模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用后缀数组解决一道模板题并解释每个数组含义。

卡 10：后缀自动机#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或后缀自动机。
优先模板：使用后缀自动机模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用后缀自动机解决一道模板题并解释每个数组含义。

卡 11：回文自动机#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或回文自动机。
优先模板：使用回文自动机模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用回文自动机解决一道模板题并解释每个数组含义。

卡 12：最小表示法#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或最小表示法。
优先模板：使用最小表示法模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用最小表示法解决一道模板题并解释每个数组含义。

卡 13：字典序比较#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或字典序比较。
优先模板：使用字典序比较模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用字典序比较解决一道模板题并解释每个数组含义。

卡 14：LCP 查询#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 LCP 查询。
优先模板：使用 LCP 查询模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 LCP 查询解决一道模板题并解释每个数组含义。

卡 15：多模式匹配#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或多模式匹配。
优先模板：使用多模式匹配模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用多模式匹配解决一道模板题并解释每个数组含义。

卡 16：禁串 DP#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或禁串 DP。
优先模板：使用禁串 DP 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用禁串 DP 解决一道模板题并解释每个数组含义。

卡 17：循环同构#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或循环同构。
优先模板：使用循环同构模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用循环同构解决一道模板题并解释每个数组含义。

卡 18：最长重复子串#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或最长重复子串。
优先模板：使用最长重复子串模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用最长重复子串解决一道模板题并解释每个数组含义。

卡 19：不同子串计数#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或不同子串计数。
优先模板：使用不同子串计数模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用不同子串计数解决一道模板题并解释每个数组含义。

卡 20：前缀周期#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或前缀周期。
优先模板：使用前缀周期模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用前缀周期解决一道模板题并解释每个数组含义。

卡 21：border 树#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或 border 树。
优先模板：使用 border 树模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用 border 树解决一道模板题并解释每个数组含义。

卡 22：字符串 DP#

题目信号：题目涉及匹配、前缀、回文、子串、字典序或字符串 DP。
优先模板：使用字符串 DP 模板。
核心不变量：已匹配信息或自动机状态能被复用，不重复扫描。
复杂度目标：多数基础字符串模板 O(n)，AC 自动机 O(总长度 + 文本长度)。
不适用场景：字符集巨大、动态修改或哈希碰撞要求严格证明时要换模型。
实现检查：检查下标换算、分隔符、fail 指针、取模负数。
边界样例：空串、单字符、全相同字符、模式串等于文本。
训练题型：用字符串 DP 解决一道模板题并解释每个数组含义。

本章赛前默写任务#

字符串算法赛场自检表#

09_字符串算法：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：KMP#

识别信号：题面出现与“KMP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“KMP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：Z 函数#

识别信号：题面出现与“Z 函数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Z 函数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：Trie#

识别信号：题面出现与“Trie”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Trie”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：01 Trie#

识别信号：题面出现与“01 Trie”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“01 Trie”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：字符串哈希#

识别信号：题面出现与“字符串哈希”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“字符串哈希”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：双哈希#

识别信号：题面出现与“双哈希”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“双哈希”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：Manacher#

识别信号：题面出现与“Manacher”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Manacher”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：AC 自动机#

识别信号：题面出现与“AC 自动机”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“AC 自动机”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：后缀数组#

识别信号：题面出现与“后缀数组”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“后缀数组”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：后缀自动机#

识别信号：题面出现与“后缀自动机”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“后缀自动机”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：回文自动机#

识别信号：题面出现与“回文自动机”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“回文自动机”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：最小表示法#

识别信号：题面出现与“最小表示法”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“最小表示法”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：LCP#

识别信号：题面出现与“LCP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“LCP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：border#

识别信号：题面出现与“border”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“border”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：周期#

识别信号：题面出现与“周期”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“周期”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：禁串 DP#

识别信号：题面出现与“禁串 DP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“禁串 DP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：KMP#

识别信号：题面出现与“KMP”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“KMP”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：Z 函数#

识别信号：题面出现与“Z 函数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Z 函数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：Trie#

识别信号：题面出现与“Trie”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Trie”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：01 Trie#

识别信号：题面出现与“01 Trie”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“01 Trie”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：字符串哈希#

识别信号：题面出现与“字符串哈希”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“字符串哈希”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 22：双哈希#

识别信号：题面出现与“双哈希”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“双哈希”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 23：Manacher#

识别信号：题面出现与“Manacher”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Manacher”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 24：AC 自动机#

识别信号：题面出现与“AC 自动机”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“AC 自动机”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

ぬくぬくうちにゃ💤

第 9 章 字符串算法#