AC 自动机（Aho-Corasick）= Trie + KMP 的 fail 指针，实现多模式串匹配：在文本中同时查找所有模式串，时间 O(n + 总模式长 + 匹配数)。
加载中…
应用场景：多模式串匹配 · 敏感词过滤
AC 自动机（Aho-Corasick）= Trie + KMP 的 fail 指针，实现多模式串匹配：在文本中同时查找所有模式串，时间 O(n + 总模式长 + 匹配数)。
交互式动画演示，可调整参数并单步执行。
全屏打开对每个模式单独 KMP → O(n × k)；AC 自动机 → O(n + Σm)。
int[][] next = new int[MAXNODE][26];
int[] fail = new int[MAXNODE];
int[] count = new int[MAXNODE]; // 记录哪些模式在此结束
int tot = 0;
void insert(String s, int id) {
int p = 0;
for (char c : s.toCharArray()) {
int idx = c - 'a';
if (next[p][idx] == 0) next[p][idx] = ++tot;
p = next[p][idx];
}
count[p]++; // 或记录 id
}fail[u] = 当 u 失配时跳转到的最长后缀节点（类似 KMP 的 next）。
void buildFail() {
Queue<Integer> queue = new LinkedList<>();
// 第一层：fail 指向根
for (int c = 0; c < 26; c++) {
if (next[0][c] != 0) {
fail[next[0][c]] = 0;
queue.offer(next[0][c]);
}
}
while (!queue.isEmpty()) {
int u = queue.poll();
for (int c = 0; c < 26; c++) {
int v = next[u][c];
if (v != 0) {
fail[v] = next[fail[u]][c]; // 关键！
queue.offer(v);
} else {
next[u][c] = next[fail[u]][c]; // 路径压缩（可选）
}
}
}
}int search(String text) {
int p = 0, result = 0;
for (char c : text.toCharArray()) {
p = next[p][c - 'a'];
// 沿 fail 链统计所有匹配
int tmp = p;
while (tmp != 0) {
result += count[tmp];
count[tmp] = 0; // 避免重复计数（如果只统计一次）
tmp = fail[tmp];
}
}
return result;
}模式: he, she, his, hers
Trie:
root
/ | \
h s ...
/ \ \
e i h
| | |
r s e
|
s
fail[she的e] → he的e（"she"的后缀"he"在Trie中）
| 阶段 | 时间 |
|---|---|
| 建 Trie | O(Σm)（所有模式总长） |
| 建 fail | O(Σm × 字符集) |
| 匹配 | O(n × 字符集) 或 O(n + 匹配数) |
next[u][c] = next[fail[u]][c]（空边补全），匹配时 O(n)fail[child] = next[fail[parent]][c]以模式集 {he, she, his, hers} 为例，在 Trie 上构建 fail 指针：
Trie 结构（数字为节点）：
0(root)
/ | \
h s ...
/ \ \
1(e) 3(i) ...
| |
... 4(s)
fail 指针构建（BFS 逐层）：
- 第1层节点：fail = root
- 节点 "she" 的 e 节点：
fail["she"] = next[fail["sh"]][e] = next["h"][e] = "he" 节点
→ "she" 的后缀 "he" 恰好也是一个模式！
匹配 "ushers" 时：
u→s→h→e→r→s
走到 "she" 时，沿 fail 链发现 "he" 也匹配
→ 一次扫描同时找到 she, he, hers 三个模式 ✓
核心直觉：fail 指针让“当前匹配失败时，跳到另一个最长后缀继续”，与 KMP 的 next 数组思想完全一致，只是从“字符串”搬到了“Trie”。