引言

在字符串处理中，最经典的问题莫过于模式匹配：给定一个文本串和一个模式串，找出模式串在文本串中的所有出现位置。最朴素的做法是暴力匹配——每次失配后，模式串整体后移一位重新开始比较。这个方法在最坏情况下的复杂度是 O(n×m)，当字符串长度达到 10⁵ 甚至 10⁶ 时，根本无法接受。

KMP 算法（Knuth-Morris-Pratt） 的诞生彻底改变了这一局面。它通过预处理模式串，构建一个 next 数组（或称前缀函数），在失配时能够“跳着走”，而不是笨拙地一步一挪，从而将匹配复杂度降为 O(n+m)。

但 KMP 只能处理单个模式串的匹配问题。如果同时有多个模式串需要匹配呢？比如在一段文本中查找若干个敏感词？AC 自动机（Aho-Corasick Automaton） 正是为此而生。它将 KMP 的失配指针思想从线性结构推广到了 Trie 树上，实现了一次扫描文本、同时匹配所有模式串的强大功能。

如果说暴力匹配是“走一步看一步”，那么 KMP 就是 “跳着走”——它记住了模式串自身的结构，失配时直接跳到下一个可能匹配的位置。而 AC 自动机则是 “在树上跳着走”——它把多个模式串组织成一棵树，失配时沿着树上的“捷径”跳跃，一次扫描就能命中所有目标。

---

前置知识

在学习 KMP 和 AC 自动机之前，你需要掌握以下基础：

1. 字符串的基本概念：前缀、后缀、子串、真前缀/真后缀。

2. Trie 树（字典树）：一种用于高效存储和查找字符串集合的树形数据结构。AC 自动机建立在 Trie 树之上。

3. 队列（BFS）：AC 自动机构建 fail 指针时使用广度优先搜索。

4. 递归与DFS：理解 fail 树和在 AC 自动机上做 DP 时需要。

---

第一章：KMP算法——单模式匹配的“跳跃者”

1.1 从暴力到KMP：为什么要“跳”？

考虑文本串 s = "aaaaaaaaab"，模式串 p = "aaaab"。暴力匹配时，每次在最后一个字符 'b' 处失配后，模式串只能整体后移一位，然后从模式串的第一个字符重新开始比较。这导致大量重复比较——明明前面四个 'a' 已经匹配过了，为什么不能利用这个信息？

KMP 的核心洞察是：失配时，模式串不需要从头开始。如果模式串的某个前缀和已经匹配的文本后缀相同，那么模式串可以直接滑动到这个位置继续比较。

1.2 next 数组的定义

next[i]（或称 pi[i]）表示模式串 p[0...i-1] 的最长公共真前后缀的长度。换句话说，它是 p 的前 i 个字符组成的子串中，既是前缀又是后缀的最长长度（且长度小于 i）。

例如 p = "ababa"：

• next[0] = -1（约定）

• next[1] = 0（"a" 没有真前后缀）

• next[2] = 0（"ab" 没有）

• next[3] = 1（"aba" 的前缀 "a" = 后缀 "a"）

• next[4] = 2（"abab" 的前缀 "ab" = 后缀 "ab"）

• next[5] = 3（"ababa" 的前缀 "aba" = 后缀 "aba"）

1.3 如何求解 next 数组

求解 next 数组的过程，本质上是模式串与自身进行匹配。

设 j 表示当前已匹配的前缀长度，初始 j = 0。从 i = 2 开始遍历模式串（假设下标从 1 开始）：

for (int i = 2; i <= m; i++) {
    while (j && p[i] != p[j + 1]) j = nxt[j];
    if (p[i] == p[j + 1]) j++;
    nxt[i] = j;
}

递推逻辑：

• 已知 next[j] = k，表示 p[0...k-1] = p[j-k...j-1]。

• 求 next[j+1] 时，只需比较 p[k] 与 p[j]：

  • 若相等，则 next[j+1] = k + 1。

  • 若不相等，则令 k = next[k]，继续比较（递归地寻找更短的相同前后缀）。

1.4 KMP 匹配过程

有了 next 数组，匹配就变得简单了：

for (int i = 1; i <= n; i++) {
    while (j && s[i] != p[j + 1]) j = nxt[j];
    if (s[i] == p[j + 1]) j++;
    if (j == m) {
        // 匹配成功，位置为 i - m + 1
        j = nxt[j];  // 继续寻找下一个匹配
    }
}

复杂度：构建 next 数组 O(m)，匹配过程 O(n)，总复杂度 O(n+m)。

---

第二章：AC自动机——多模式匹配的“树上游侠”

2.1 从KMP到AC自动机

KMP 解决了一个模式串的匹配问题。但如果模式串有多个（比如敏感词列表），对每个模式串分别跑一次 KMP，复杂度为 O(n × k)，其中 k 是模式串数量，显然不可行。

AC 自动机的思路是：把所有模式串插入到一棵 Trie 树中，然后在树上做 KMP。

如果说 KMP 的 next 数组是在一条线上“跳”，那么 AC 自动机的 fail 指针就是在树上“跳”——从当前节点跳到另一个节点，使得跳转后的字符串是当前匹配串的最长后缀。

2.2 构建 Trie 树

首先将所有模式串插入到一棵 Trie 树中：

int tr[N][26], tot;
void insert(string s) {
    int u = 0;
    for (char c : s) {
        int v = c - 'a';
        if (!tr[u][v]) tr[u][v] = ++tot;
        u = tr[u][v];
    }
    cnt[u]++;  // 标记该节点是一个模式串的结尾
}

2.3 fail 指针的定义

在 KMP 中，next[j] 表示失配后模式串应该跳到的位置。在 AC 自动机中，fail 指针扮演了相同的角色：

fail[u] 指向Trie 中存在的最长的、是 u 所代表字符串的真后缀的那个节点。

例如，模式串集合为 {"he", "she", "his", "hers"}，节点 "she" 的 fail 指针指向 "he"，因为 "he" 是 "she" 的最长后缀且出现在 Trie 中。

重要性质：所有 fail 指针构成一棵树，称为 fail 树。这棵树在后来的许多应用中非常关键。

2.4 如何求解 fail 指针

求解 fail 指针使用 BFS（广度优先搜索）：

void build() {
    queue<int> q;
    // 初始化：根节点(0)的所有非空子节点的 fail 指向根
    for (int i = 0; i < 26; i++) {
        if (tr[0][i]) {
            fail[tr[0][i]] = 0;
            q.push(tr[0][i]);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr[u][i];
            if (v) {
                // 核心：v 的 fail 指向 u 的 fail 的 i 儿子
                fail[v] = tr[fail[u]][i];
                q.push(v);
            } else {
                // 优化：将不存在的转移直接指向 fail 的对应转移
                tr[u][i] = tr[fail[u]][i];
            }
        }
    }
}

理解这段代码：

• 对于节点 u 的字符 i 儿子 v，v 的 fail 指针应该指向 fail[u] 的 i 儿子。这相当于在 Trie 树上“递归地”寻找最长后缀。

• 如果 u 没有字符 i 的儿子，我们直接把 tr[u][i] 设置为 tr[fail[u]][i]。这一步称为 “补全转移” ，它让 AC 自动机变成了一个完整的 DFA（确定性有限自动机） ——无论输入什么字符，从任何状态出发都一定有转移。

2.5 多模式匹配

匹配时，只需在补全后的自动机上走一遍文本串：

int query(string s) {
    int u = 0, ans = 0;
    for (char c : s) {
        int v = c - 'a';
        u = tr[u][v];  // 直接转移（已被补全）
        // 统计所有以当前匹配后缀结尾的模式串
        for (int t = u; t && cnt[t] != -1; t = fail[t]) {
            ans += cnt[t];
            cnt[t] = -1;  // 防止重复计数
        }
    }
    return ans;
}

复杂度：建 Trie O(Σ|模式串|)，建 fail O(Σ|模式串| × 字符集大小)，匹配 O(|文本串| + 匹配次数)。

---

第三章：fail树——失配指针的“家族谱系”

3.1 什么是 fail 树？

所有节点的 fail 指针构成一棵以根节点为根的树。在这棵树中，每个节点的父节点就是它的 fail 指针指向的节点。

如果把 AC 自动机的节点看作“状态”，那么 fail 树描述的是状态之间的“后缀包含关系”——u 的 fail 链上的所有节点，都是 u 所代表字符串的后缀。

3.2 fail 树的应用

fail 树将 AC 自动机的问题转化为了树上问题，可以用树链剖分、树上差分、DFS 序等技巧来解决。

典型应用：统计每个模式串在文本串中出现的次数。

朴素做法是：每匹配到一个节点 u，就暴力跳 fail 链统计答案。但这样最坏复杂度是 O(n × 树高)，可能退化到 O(n²)。

优化方法：

1. 匹配时，只在每个到达的节点 u 上打一个标记 +1。

2. 匹配结束后，在 fail 树上做子树求和——节点 u 的答案等于其 fail 子树中所有标记的和。

3. 这是因为：如果某个节点 v 被标记了，那么所有 fail 树上 v 的祖先（即 v 的后缀）都应该被统计到。

3.3 例题：洛谷 P5357 【模板】AC自动机（二次加强版）

这道题要求统计每个模式串在文本串中出现的次数。正解就是：建 AC 自动机，匹配时打标记，最后在 fail 树上 DFS 做子树求和。

---

第四章：在AC自动机上做DP

AC 自动机不仅是一个匹配工具，还可以作为 DP 的状态图来使用。这是许多难题的突破口。

4.1 核心思想

把 AC 自动机的每个节点看作一个 DP 状态，表示“当前已经匹配到自动机上的哪个节点”。在自动机上每走一步（读入一个字符），就转移到下一个状态。同时，某些状态可能是“危险状态”（即匹配到了某个模式串），在 DP 中需要避免或特殊处理。

4.2 典型模型

模型一：不包含任何模式串的字符串计数

给定若干个模式串，求长度为 L 的、不包含任何模式串作为子串的字符串数量。

解法：

• 建 AC 自动机，标记所有模式串的结尾节点及其 fail 树上的所有祖先为“危险节点”。

• 设 dp[i][u] 表示长度为 i、当前在节点 u 的合法字符串数量。

• 转移：dp[i+1][tr[u][c]] += dp[i][u]，要求 tr[u][c] 不是危险节点。

• 最终答案：Σ dp[L][u]（所有非危险节点）。

模型二：包含至少一个模式串的期望/计数

通常用容斥或矩阵快速幂（当 L 很大时）处理。

---

第五章：例题与详细解析

例题1：KMP模板 —— 洛谷 P3375

题目描述
给定两个字符串 s1（文本串）和 s2（模式串），求出 s2 在 s1 中所有出现的位置，并输出 s2 的每个前缀的最长 border 长度。

解题思路
这是 KMP 的纯模板题。需要实现两个功能：

1. 计算 s2 的 next 数组（即每个前缀的最长 border 长度）。

2. 用 KMP 在 s1 中匹配 s2，记录所有匹配位置。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int nxt[N], n, m;

int main() {
    string s, p;
    cin >> s >> p;
    n = s.size(), m = p.size();
    s = " " + s, p = " " + p;  // 下标从1开始
    
    // 求 next 数组
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = nxt[j];
        if (p[i] == p[j + 1]) j++;
        nxt[i] = j;
    }
    
    // KMP 匹配
    for (int i = 1, j = 0; i <= n; i++) {
        while (j && s[i] != p[j + 1]) j = nxt[j];
        if (s[i] == p[j + 1]) j++;
        if (j == m) {
            cout << i - m + 1 << '\n';  // 匹配位置
            j = nxt[j];
        }
    }
    
    // 输出 next 数组
    for (int i = 1; i <= m; i++) cout << nxt[i] << " ";
    return 0;
}

解析：

• 下标从 1 开始是为了方便处理边界。

• nxt[1] = 0 是默认的，循环从 i = 2 开始。

• 匹配成功后将 j 回退到 nxt[j]，以便寻找下一个重叠匹配。

---

例题2：AC自动机模板 —— 洛谷 P3808

题目描述
给定 n 个模式串和一个文本串，问有多少个模式串在文本串中出现过。

解题思路
这是 AC 自动机的最基础应用。建 Trie 树，构建 fail 指针，然后在文本串上跑匹配，统计有多少个模式串被匹配到。

注意事项：

• 本题数据中有重复的模式串，重复的单词应该计算多次。但题目问的是“有多少个模式串出现过”，所以重复的只需要统计一次即可。

• 匹配时访问过的节点要标记，避免重复计数。

代码实现（核心部分）

struct Node {
    int ch[26], fail, cnt;
} tr[N];

void insert(string s) {
    int u = 0;
    for (char c : s) {
        int v = c - 'a';
        if (!tr[u].ch[v]) tr[u].ch[v] = ++tot;
        u = tr[u].ch[v];
    }
    tr[u].cnt++;  // 可能有重复模式串，用 cnt 计数
}

void build() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        if (tr[0].ch[i]) {
            tr[tr[0].ch[i]].fail = 0;
            q.push(tr[0].ch[i]);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr[u].ch[i];
            if (v) {
                tr[v].fail = tr[tr[u].fail].ch[i];
                q.push(v);
            } else {
                tr[u].ch[i] = tr[tr[u].fail].ch[i];
            }
        }
    }
}

int query(string s) {
    int u = 0, ans = 0;
    for (char c : s) {
        u = tr[u].ch[c - 'a'];
        for (int t = u; t && tr[t].cnt != -1; t = tr[t].fail) {
            ans += tr[t].cnt;
            tr[t].cnt = -1;  // 标记已访问
        }
    }
    return ans;
}

解析：

• build() 中处理 tr[u].ch[i] = tr[tr[u].fail].ch[i] 完成了自动机的“补全”。

• query() 中暴力跳 fail 链是可行的，因为每个节点最多被访问一次（cnt 被设为 -1 后不再访问）。

---

例题3：病毒 —— 洛谷 P2444

题目描述
给定若干个 01 字符串作为“病毒代码”，问是否存在一个无限长的 01 字符串，使得其中不包含任何一段病毒代码。

解题思路
这是一道 AC 自动机的思维变形题。关键在于将问题转化为图论中的环检测问题。

步骤：

1. 建 AC 自动机：将所有病毒代码插入 Trie 树，构建 fail 指针。

2. 标记危险节点：一个节点是“危险”的，当且仅当：

   • 它本身是某个病毒代码的结尾节点；或

   • 它的 fail 链上有危险节点。

   这是因为如果当前匹配到的字符串的后缀是病毒代码，那么这个字符串本身就包含了病毒。

3. 找环：在 AC 自动机上，从根节点出发，沿着非危险节点的转移边走，看是否能形成一个环。

   • 如果能形成环，说明可以在这个环上无限循环，构造出无限长的安全代码。

   • 如果不能，说明所有路径最终都会走到危险节点，不存在无限长的安全代码。

代码实现（核心）

const int MAXN = 30005;
int ch[MAXN][2], fail[MAXN], tot;
bool danger[MAXN], vis[MAXN], ins[MAXN];

void insert(string s) {
    int u = 0;
    for (char c : s) {
        int v = c - '0';
        if (!ch[u][v]) ch[u][v] = ++tot;
        u = ch[u][v];
    }
    danger[u] = true;
}

void build() {
    queue<int> q;
    for (int i = 0; i < 2; i++) {
        if (ch[0][i]) q.push(ch[0][i]);
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 2; i++) {
            if (ch[u][i]) {
                fail[ch[u][i]] = ch[fail[u]][i];
                danger[ch[u][i]] |= danger[fail[ch[u][i]]];  // 传递危险标记
                q.push(ch[u][i]);
            } else {
                ch[u][i] = ch[fail[u]][i];
            }
        }
    }
}

// DFS 找环
bool dfs(int u) {
    ins[u] = true;
    for (int i = 0; i < 2; i++) {
        int v = ch[u][i];
        if (danger[v]) continue;
        if (ins[v]) return true;  // 找到环
        if (!vis[v]) {
            vis[v] = true;
            if (dfs(v)) return true;
        }
    }
    ins[u] = false;
    return false;
}

解析：

• 危险标记需要通过 fail 链传递。

• 找环时用 ins 数组记录当前 DFS 栈中的节点，检测到重复访问即说明有环。

• 根节点 0 是安全的起始点。

---

第六章：拓展与应用

6.1 拓扑排序优化匹配统计

在需要统计每个模式串出现次数的题目中（如 P5357），暴力跳 fail 链可能超时。优化方法是：

1. 匹配时只在节点上打标记。

2. 按 fail 树的拓扑序（即 BFS 序的逆序）从叶子向上累加标记。

6.2 AC自动机 + 矩阵快速幂

当需要统计长度为 L 的不包含任何模式串的字符串数量，且 L 很大（如 10⁹）时，可以将 AC 自动机的转移图写成邻接矩阵，然后用矩阵快速幂加速 DP。

6.3 可持久化AC自动机

支持在 Trie 树上进行持久化操作，实现可回溯的字符串匹配。

6.4 与后缀自动机（SAM）的对比

• AC 自动机：处理多个模式串在一个文本串中的匹配，基于 Trie + fail。

• 后缀自动机：处理一个模式串在多个文本串中的匹配，或处理一个字符串的所有子串信息。

两者各有侧重，互为补充。

---

总结

KMP 和 AC 自动机是字符串匹配领域的两座里程碑。KMP 用 next 数组实现了单模式串的线性匹配，而 AC 自动机将其思想推广到 Trie 树上，实现了多模式串的同时匹配。

学习它们的要点：

1. 理解 next/fail 的本质：它们记录的是“失配后往哪跳”，本质是最长公共前后缀的信息。

2. 掌握 BFS 构建 fail 的过程：这是 AC 自动机的核心，理解了它就等于理解了 AC 自动机。

3. 认识 fail 树：它将 AC 自动机的问题转化为树上问题，是许多高级应用的基础。

4. 灵活运用自动机上的 DP：AC 自动机是一个天然的 DFA，可以在上面进行各种 DP。