企业官网建设流程全解析

引言

在字符串处理中，最经典的问题莫过于模式匹配：给定一个文本串和一个模式串，找出模式串在文本串中的所有出现位置。最朴素的做法是暴力匹配——每次失配后，模式串整体后移一位重新开始比较。这个方法在最坏情况下的复杂度是 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。