Skip to content

Commit 1a76b45

Browse files
itchargeitcharge
committed
Merge branch 'main' of https://github.com/itcharge/AlgoNote 
2 parents bbbac11 + 9dbc13d commit 1a76b45

File tree

2 files changed

+462
-70
lines changed

2 files changed

+462
-70
lines changed

‎docs/04_string/04_09_ac_automaton.md

Lines changed: 189 additions & 70 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,45 @@
11
## 1. AC 自动机简介
22

3-
> **AC 自动机（Aho-Corasick Automaton）**：该算法在 1975 年产生于贝尔实验室，是最著名的多模式匹配算法之一。简单来说，AC 自动机是以 **字典树（Trie）** 的结构为基础，结合 **KMP 算法思想** 建立的。
3+
> **AC 自动机（Aho-Corasick Automaton）**：由 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年在贝尔实验室提出，是最著名的多模式匹配算法之一。
4+
>
5+
> - **AC 自动机核心思想**：以 **字典树（Trie）** 为基础，结合 **KMP 算法的失配指针思想**，构建一个能够同时匹配多个模式串的有限状态自动机。当在文本串中匹配失败时，通过失配指针快速跳转到下一个可能匹配的状态，避免重复比较，实现高效的多模式匹配。
6+
7+
### 1.1 多模式匹配的难点
8+
9+
在实际应用中，常常需要在文本中一次性查找多个模式串（如敏感词过滤、病毒检测、DNA 序列分析等）。
10+
11+
传统的单模式匹配算法（如 KMP、Boyer-Moore）需要对每个模式串分别进行匹配，时间复杂度为 $O(n \times m \times k)$，其中 $n$ 为文本长度，$m$ 为模式串平均长度，$k$ 为模式串数量，整体效率较低。
12+
13+
如果只使用字典树（Trie），虽然能够共享前缀，但每次匹配失败都必须回到根节点重新开始，无法实现高效跳转，最坏情况下复杂度也接近 $O(n \times m)$。
14+
15+
416

5-
AC 自动机的构造有 3 个步骤：
617

7-
1. 构造一棵字典树（Trie），作为 AC 自动机的搜索数据结构。
8-
2. 利用 KMP 算法思想，构造失配指针。使得当前字符失配时可以通过失配指针跳转到具有最长公共前后缀的字符位置上继续匹配。
9-
3. 扫描文本串进行匹配。
18+
### 1.2 AC 自动机高效匹配原理
19+
20+
AC 自动机能够高效解决多模式匹配问题，其核心思想是：将所有模式串构建为一棵字典树（Trie），并为每个节点设置失配指针（fail 指针），结合 KMP 算法的失配机制，实现对文本串的一次扫描即可同时匹配多个模式串。
21+
22+
AC 自动机的主要流程如下：
23+
24+
1. **构建字典树（Trie）**：将所有模式串插入字典树，充分利用公共前缀，节省空间和比较次数。
25+
2. **构建失配指针（fail 指针）**：借鉴 KMP 算法思想，为字典树中每个节点添加失配指针。失配指针指向当前节点对应字符串的最长可用后缀节点，实现匹配失败时的快速跳转，避免重复比较。
26+
3. **一次扫描文本串进行匹配**：只需从头到尾扫描一遍文本串，利用字典树和失配指针的协同作用，即可高效找到所有模式串的出现位置。
27+
28+
AC 自动机的时间复杂度为 $O(n + m + k)$，其中 $n$ 为文本串长度，$m$ 为所有模式串的总长度，$k$ 为匹配到的模式串数量。相比传统的多模式串逐一匹配方法（如 $O(n \times m \times k)$），AC 自动机大幅提升了匹配效率。
1029

1130
## 2. AC 自动机原理
1231

13-
接下来我们以一个例子来说明一下 AC 自动机的原理。
32+
下面用一个简单例子来直观理解 AC 自动机的原理。
1433

15-
> 描述：给定 5 个单词，分别是 `say`、`she`、`shr`、`he`、`her`，再给定一个文本串 `yasherhs`。
34+
> **例子**：给定 5 个模式串：`say`、`she`、`shr`、`he`、`her`，文本串为 `yasherhs`。
1635
>
17-
> 要求：计算出有多少个单词在文本串中出现过。
36+
> **目标**：找出文本中所有出现的模式串及其位置。
1837
19-
### 2.1 构造一棵字典树（Trie）
38+
### 2.1 构建字典树（Trie）
2039

21-
首先我们需要建立一棵字典树。字典树是一种树形数据结构，用于高效地存储和检索字符串集合。每个节点代表一个字符，从根节点到某个节点的路径上的字符连接起来，就是该节点对应的字符串。
40+
我们先把所有模式串插入到一棵字典树中。字典树就像一棵「分叉的路」，每个节点代表一个字符，从根到某节点的路径，就是一个字符串。
2241

23-
对于给定的 5 个单词，构造的字典树如下：
42+
以这 5 个模式串为例，字典树结构如下：
2443

2544
```
2645
root
@@ -34,103 +53,203 @@ AC 自动机的构造有 3 个步骤：
3453

3554
### 2.2 构造失配指针
3655

37-
失配指针（fail pointer）是 AC 自动机的核心。当在字典树中匹配失败时，失配指针指向另一个节点，该节点对应的字符串是当前节点对应字符串的最长后缀。
56+
失配指针（fail 指针）是 AC 自动机的关键。它借鉴 KMP 算法的思想，为每个节点指向其「最长可用后缀」在字典树中的节点，实现失配时的快速跳转。
57+
58+
#### 2.2.1 失配指针的定义
59+
60+
对于字典树中的任意节点，其失配指针指向该节点对应字符串的 **最长真后缀** 在字典树中的节点。
3861

39-
失配指针的构造过程：
40-
1. 根节点的失配指针指向空
41-
2. 对于每个节点，其失配指针指向其父节点的失配指针指向的节点的对应子节点
42-
3. 如果对应子节点不存在，则继续沿着失配指针向上查找
62+
- **真后缀**：字符串的真后缀是指该字符串的后缀，但不等于字符串本身。
4363

44-
### 2.3 扫描文本串
64+
#### 2.2.2 构造规则
4565

46-
扫描文本串的过程：
47-
1. 从根节点开始，按照文本串的字符顺序在字典树中移动
48-
2. 如果当前字符匹配成功，继续移动到下一个字符
49-
3. 如果当前字符匹配失败，通过失配指针跳转到另一个节点继续匹配
50-
4. 当到达某个单词的结束节点时，说明找到了一个匹配的单词
66+
失配指针的构造遵循以下规则：
5167

52-
## 3. AC 自动机的应用
68+
1. **根节点**：失配指针为 `null`
69+
2. **根节点的子节点**：失配指针都指向根节点
70+
3. **其他节点**：从父节点的失配指针开始查找，如果找到对应字符的子节点，则指向该子节点；否则继续向上查找，直到找到或到达根节点
71+
72+
#### 2.2.3 构造示例
73+
74+
以模式串 `["say", "she", "shr", "he", "her"]` 为例：
75+
76+
```
77+
root
78+
/ \
79+
s h
80+
/ \ |
81+
a h e
82+
/ / \ \
83+
y e r r
84+
```
5385

54-
AC 自动机在以下场景中有着广泛的应用：
86+
**失配指针构造过程**：
87+
- `s` → `root`（根节点子节点指向根节点）
88+
- `h` → `root`（根节点子节点指向根节点）
89+
- `sa` → `root`（根节点没有 `a` 子节点）
90+
- `sh` → `h`（根节点有 `h` 子节点）
91+
- `he` → `e`（根节点有 `e` 子节点）
92+
- `hr` → `root`（根节点没有 `r` 子节点）
93+
- `say` → `root`（根节点没有 `y` 子节点）
94+
- `she` → `he`（`h` 节点有 `e` 子节点）
95+
- `shr` → `root`（`h` 和根节点都没有 `r` 子节点）
96+
- `her` → `root`（`e` 和根节点都没有 `r` 子节点）
5597

56-
1. **多模式字符串匹配**：在文本中查找多个模式串
57-
2. **敏感词过滤**：检测文本中是否包含敏感词
58-
3. **DNA序列分析**：在生物信息学中用于DNA序列的模式匹配
59-
4. **网络入侵检测**：检测网络数据包中的恶意模式
60-
5. **拼写检查**：检查文本中的拼写错误
98+
#### 2.2.4 失配指针的作用
6199

62-
## 4. AC 自动机的实现
100+
失配指针的主要作用是：
101+
1. **快速跳转**：匹配失败时，不需要回到根节点重新开始
102+
2. **避免重复比较**：利用已匹配的部分信息，避免重复比较
103+
3. **保证匹配连续性**：确保跳转后当前匹配的字符串仍是某个模式串的前缀
63104

64-
### 4.1 时间复杂度
105+
### 2.3 文本串匹配过程
65106

66-
- 构建字典树：O(Σ|P|)，其中 P 是所有模式串的集合
67-
- 构建失配指针：O(Σ|P|)
68-
- 文本串匹配：O(n + k)，其中 n 是文本串长度，k 是匹配的模式串数量
107+
有了字典树和失配指针，我们就可以进行高效的文本串匹配了。
69108

70-
### 4.2 空间复杂度
109+
#### 2.3.1 匹配算法流程
71110

72-
- O(Σ|P|)，其中 Σ 是字符集大小
111+
1. **初始化**：从根节点开始
112+
2. **字符匹配**：对于文本串中的每个字符：
113+
- 如果当前节点有对应字符的子节点，移动到该子节点
114+
- 否则，沿着失配指针向上查找，直到找到匹配的子节点或到达根节点
115+
3. **模式串检测**：每到达一个节点，检查该节点是否为某个模式串的结尾
116+
4. **输出匹配结果**：如果找到匹配的模式串，记录其位置和内容
117+
118+
#### 2.3.2 匹配过程示例
119+
120+
以文本串 `yasherhs` 为例，演示匹配过程：
121+
122+
| 字符 | 当前节点 | 操作 | 当前路径 | 匹配结果 |
123+
|------|----------|------|----------|----------|
124+
| `y` | 根节点 | 无匹配，保持根节点 | - | - |
125+
| `a` | 根节点 | 无匹配，保持根节点 | - | - |
126+
| `s` | 根节点 | 移动到 `s` 节点 | `s` | - |
127+
| `h` | `s` 节点 | 移动到 `sh` 节点 | `sh` | - |
128+
| `e` | `sh` 节点 | 移动到 `she` 节点 | `she` | **找到 `she`** |
129+
| `r` | `she` 节点 | 失配，跳转到根节点 | - | - |
130+
| `h` | 根节点 | 移动到 `h` 节点 | `h` | - |
131+
| `s` | `h` 节点 | 失配，跳转到根节点，再移动到 `s` 节点 | `s` | - |
132+
133+
**最终结果**：在文本串 `yasherhs` 中找到模式串 `she`（位置 2-4）。
134+
135+
136+
## 3. AC 自动机代码实现
73137

74-
## 5. 代码实现
75138

76139
```python
77140
class TrieNode:
78141
def __init__(self):
79-
self.children = {} # 子节点
80-
self.fail = None # 失配指针
81-
self.is_end = False # 是否是单词结尾
82-
self.word = "" # 存储完整的单词
142+
self.children = {} # 子节点，key 为字符，value 为 TrieNode
143+
self.fail = None # 失配指针，指向当前节点最长可用后缀的节点
144+
self.is_end = False # 是否为某个模式串的结尾
145+
self.word = "" # 如果是结尾，存储完整的单词
83146

84147
class AC_Automaton:
85148
def __init__(self):
86-
self.root = TrieNode()
87-
149+
self.root = TrieNode() # 初始化根节点
150+
88151
def add_word(self, word):
152+
"""
153+
向Trie树中插入一个模式串
154+
"""
89155
node = self.root
90156
for char in word:
91157
if char not in node.children:
92-
node.children[char] = TrieNode()
158+
node.children[char] = TrieNode() # 新建子节点
93159
node = node.children[char]
94-
node.is_end = True
95-
node.word = word
96-
160+
node.is_end = True # 标记单词结尾
161+
node.word = word # 存储完整单词
162+
97163
def build_fail_pointers(self):
98-
queue = []
99-
# 将根节点的子节点的失配指针指向根节点
100-
for char, node in self.root.children.items():
101-
node.fail = self.root
102-
queue.append(node)
103-
104-
# 广度优先搜索构建失配指针
164+
"""
165+
构建失配指针（fail指针），采用BFS广度优先遍历
166+
"""
167+
from collections import deque
168+
queue = deque()
169+
# 1. 根节点的所有子节点的 fail 指针都指向根节点
170+
for child in self.root.children.values():
171+
child.fail = self.root
172+
queue.append(child)
173+
174+
# 2. 广度优先遍历，依次为每个节点建立 fail 指针
105175
while queue:
106-
current = queue.pop(0)
176+
current = queue.popleft()
107177
for char, child in current.children.items():
178+
# 从当前节点的 fail 指针开始，向上寻找有无相同字符的子节点
108179
fail = current.fail
109180
while fail and char not in fail.children:
110181
fail = fail.fail
111-
child.fail = fail.children[char] if fail else self.root
182+
# 如果找到了，child的fail指针指向该节点，否则指向根节点
183+
child.fail = fail.children[char] if fail and char in fail.children else self.root
112184
queue.append(child)
113-
185+
114186
def search(self, text):
187+
"""
188+
在文本text中查找所有模式串出现的位置
189+
返回所有匹配到的模式串（可重复）
190+
"""
115191
result = []
116-
current = self.root
117-
118-
for char in text:
119-
while current is not self.root and char not in current.children:
120-
current = current.fail
121-
if char in current.children:
122-
current = current.children[char]
123-
124-
# 检查当前节点是否是某个单词的结尾
125-
temp = current
192+
node = self.root
193+
194+
for idx, char in enumerate(text):
195+
# 如果当前节点没有该字符的子节点，则沿fail指针向上跳转
196+
while node is not self.root and char not in node.children:
197+
node = node.fail
198+
# 如果有该字符的子节点，则转移到该子节点
199+
if char in node.children:
200+
node = node.children[char]
201+
# 否则仍然停留在根节点
202+
203+
# 检查当前节点以及沿fail链上的所有节点是否为单词结尾
204+
temp = node
126205
while temp is not self.root:
127206
if temp.is_end:
128-
result.append(temp.word)
207+
result.append(temp.word) # 记录匹配到的模式串
129208
temp = temp.fail
130-
209+
131210
return result
132211
```
133212

213+
214+
215+
## 4. AC 自动机算法分析
216+
217+
| 指标 | 复杂度 | 说明 |
218+
| ------------ | ---------------- | ------------------------------------------------------------ |
219+
| 构建字典树 | $O(m)$ | $m$ 为所有模式串的总长度 |
220+
| 构建失配指针 | $O(m)$ | 使用 BFS 遍历所有节点，每个节点最多被访问一次 |
221+
| 文本串匹配 | $O(n + k)$ | $n$ 为文本串长度，$k$ 为匹配到的模式串数量 |
222+
| **总体时间复杂度** | **$O(n + m + k)$** | 线性时间复杂度，非常高效 |
223+
| **空间复杂度** | $O(m)$ | 包含字典树和失配指针的存储，$m$ 为所有模式串的总长度 |
224+
225+
134226
## 6. 总结
135227

136-
AC 自动机是一种高效的多模式匹配算法，它通过结合字典树和 KMP 算法的思想，实现了在文本串中快速查找多个模式串的功能。虽然其实现相对复杂，但在需要多模式匹配的场景下，AC 自动机提供了最优的时间复杂度。
228+
AC 自动机是一种高效的多模式匹配算法，它巧妙地结合了字典树和 KMP 算法的思想，实现了在文本串中快速查找多个模式串的功能。
229+
230+
**核心思想**：
231+
- 使用字典树组织所有模式串，共享公共前缀
232+
- 借鉴 KMP 算法的失配指针思想，实现快速状态跳转
233+
- 通过一次扫描文本串，找到所有匹配的模式串
234+
235+
虽然 AC 自动机的实现相对复杂，但在需要多模式匹配的场景下，它提供了最优的时间复杂度，是处理多模式匹配问题的首选算法。
236+
237+
## 练习题目
238+
239+
- [0208. 实现 Trie (前缀树)](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0200-0299/implement-trie-prefix-tree.md)
240+
- [0677. 键值映射](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0600-0699/map-sum-pairs.md)
241+
- [1023. 驼峰式匹配](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/1000-1099/camelcase-matching.md)
242+
- [0211. 添加与搜索单词 - 数据结构设计](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0200-0299/design-add-and-search-words-data-structure.md)
243+
- [0648. 单词替换](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0600-0699/replace-words.md)
244+
- [0676. 实现一个魔法字典](https://github.com/ITCharge/AlgoNote/tree/main/docs/solutions/0600-0699/implement-magic-dictionary.md)
245+
246+
- [多模式串匹配题目列表](https://github.com/ITCharge/AlgoNote/tree/main/docs/00_preface/00_06_categories_list.md#%E5%A4%9A%E6%A8%A1%E5%BC%8F%E4%B8%B2%E5%8C%B9%E9%85%8D%E9%A2%98%E7%9B%AE)
247+
248+
## 参考资料
249+
250+
- 【书籍】算法训练营 陈小玉 著
251+
- 【书籍】ACM-ICPC 程序设计系列 算法设计与实现 陈宇 吴昊 主编
252+
- 【博文】[AC自动机 - OI Wiki](https://oi-wiki.org/string/ac-automaton/)
253+
- 【博文】[AC自动机算法详解 - 数据结构与算法之美 - 极客时间](https://time.geekbang.org/column/article/72810)
254+
- 【博文】[AC自动机算法详解 - 算法竞赛进阶指南](https://www.acwing.com/blog/content/405/)
255+
- 【博文】[AC自动机算法原理与实现 - 算法笔记](https://www.algorithm-notes.org/string/ac-automaton/)

0 commit comments

Comments
 (0)