From 1727969449c482038d2454e537dd1768a1cfaf7d Mon Sep 17 00:00:00 2001
From: sshwy <jy.cat@qq.com>
Date: Wed, 17 Jul 2019 17:56:52 +0800
Subject: [PATCH] =?utf8?q?=E6=B7=BB=E5=8A=A0KMP=E8=87=AA=E5=8A=A8=E6=9C=BA?=
 =?utf8?q?=E5=92=8C=E7=A1=AE=E5=AE=9A=E6=9C=89=E9=99=90=E7=8A=B6=E6=80=81?=
 =?utf8?q?=E8=87=AA=E5=8A=A8=E6=9C=BA=E7=9A=84=E6=8B=93=E5=B1=95?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/string/ac-automaton.md | 33 +++++++++++++++++++++++----------
 1 file changed, 23 insertions(+), 10 deletions(-)

diff --git a/docs/string/ac-automaton.md b/docs/string/ac-automaton.md
index ef5e14e1..ff1e50ce 100644
--- a/docs/string/ac-automaton.md
+++ b/docs/string/ac-automaton.md
@@ -94,7 +94,7 @@ void build() {
 
 为~~关爱萌新~~，笔者大力~~复读~~一下代码：Build 函数将结点按 BFS 顺序入队，依次求 fail 指针。这里的字典树根结点为 0，我们将根结点的子结点一一入队。若将根结点入队，则在第一次 BFS 的时候，会将根结点儿子的 fail 指针标记为本身。因此我们将根结点的儿子。
 
-然后开始 BFS：每次取出队首的结点 u。fail[u]指针已经求得，我们要求 u 的子结点们的 fail 指针。然后遍历字符集（这里是 0-25，对应 a-z）：
+然后开始 BFS：每次取出队首的结点 u。fail[u] 指针已经求得，我们要求 u 的子结点们的 fail 指针。然后遍历字符集（这里是 0-25，对应 a-z）：
 
 1.  如果 $trans(u,i)$ 存在，我们就将 $trans(u,i)$ 的 fail 指针赋值为 $trans(fail[u],i)$ 。这里似乎有一个问题。根据之前的讲解，我们应该用 while 循环，不停的跳 fail 指针，判断是否存在字符 `i` 对应的结点，然后赋值。不过在代码中我们一句话就做完这件事了。
 2.  否则， $trans(u,i)$ 不存在，就让 $trans(u,i)$ 指向 $trans(fail[u],i)$ 的状态。
@@ -160,6 +160,8 @@ int query(char *t) {
 
 ~~希望~~大家看懂了文章。其实总结一下，你只需要知道 AC 自动机的板子很好背就行啦。
 
+时间复杂度：AC 自动机的时间复杂度在需要找到所有匹配位置时是 $O(|s|+m)$ ，其中 $|s|$ 表示文本串的长度， $m$ 表示模板串的总匹配次数；而只需要求是否匹配时时间复杂度为 $O(|s|)$ 。
+
 ???+ note "模板 1"
 
     [LuoguP3808【模板】AC 自动机（简单版）](https://www.luogu.org/problemnew/show/P3808)
@@ -281,17 +283,27 @@ int query(char *t) {
     }
     ```
 
-## KMP 自动机
+## 拓展
+
+### 确定有限状态自动机
+
+如果大家理解了上面的讲解，那么做为拓展延伸，文末我们简单介绍一下自动机与 KMP 自动机。（现在你再去看百科上自动机的定义就会好懂很多啦）
 
-最后介绍自动机和 KMP 自动机，供学有余力的朋友观赏。
+有限状态自动机 （deterministic finite automaton，DFA）是由
 
-有限状态自动机 (DFA)：字符集，有限状态控制，初始状态，接受状态。
+1. 状态集合 $Q$；
+2. 字符集 $\Sigma$；
+3. 状态转移函数 $\delta:Q\times \Sigma \to Q$，即 $\delta(q,\sigma)=q',\ q,q'\in Q,\sigma\in \Sigma$；
+4. 一个开始状态 $s\in Q$；
+5. 一个接收的状态集合 $F\subseteq Q$。
 
-KMP 自动机：一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。
+组成的五元组 $(Q,\Sigma,\delta,s,F)$。
 
-共有 $m$ 个状态，第 $i$ 个状态表示已经匹配了前 $i$ 个字符。
+那这东西你用 AC 自动机理解，状态集合就是字典树（图）的结点；字符集就是`a`到`z`（或者更多）；状态转移函数就是 $trans(u,c)$ 的函数（即`tr[u,c]`）；开始状态就是字典树的根结点；接收状态就是你在字典树中标记的字符串结尾结点组成的集合。
 
-定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态， $next_{i}$ 表示[prefix function](/string/prefix-function)，则有：
+### KMP 自动机
+
+KMP 自动机就是一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。如果共有 $m$ 个状态，第 $i$ 个状态表示已经匹配了前 $i$ 个字符。那么我们定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态， $next_{i}$ 表示 [prefix function](/string/prefix-function)，则有：
 
 $$
 trans_{i,c} =
@@ -303,8 +315,9 @@ $$
 
 （约定 $next_{0}=0$ ）
 
-我们发现 $trans_{i}$ 只依赖于之前的值，所以可以跟[KMP](/string/prefix-function/##knuth-morris-pratt)一起求出来。
+我们发现 $trans_{i}$ 只依赖于之前的值，所以可以跟 [KMP](/string/prefix-function/#knuth-morris-pratt) 一起求出来。
+
+时间和空间复杂度： $O(m|\Sigma|)$ 。一些细节：走到接受状态之后立即转移到该状态的 $next$ 。
 
-时间和空间复杂度： $O(m|\Sigma|)$ 。
+对比之下，AC 自动机其实就是 Trie 上的自动机。（虽然一开始丢给你这句话可能不知所措）
 
-一些细节：走到接受状态之后立即转移到该状态的 $next$ 。
-- 
2.11.0