From 3260b1d4833b49fa30cc141b2c214cf33f29b41e Mon Sep 17 00:00:00 2001
From: sshwy <jy.cat@qq.com>
Date: Tue, 16 Jul 2019 16:01:47 +0800
Subject: [PATCH] =?utf8?q?pangu=E6=8F=92=E4=BB=B6?=
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

---
 docs/string/ac-automaton.md | 48 ++++++++++++++++++++++-----------------------
 1 file changed, 24 insertions(+), 24 deletions(-)

diff --git a/docs/string/ac-automaton.md b/docs/string/ac-automaton.md
index 27ec398b..86b9b063 100644
--- a/docs/string/ac-automaton.md
+++ b/docs/string/ac-automaton.md
@@ -1,4 +1,4 @@
-我知道，很多人在第一次看到这个东西的时侯是非常兴奋的。（别问我为什么知道）不过这个自动机啊它叫作`Automaton`，不是`Automation`，让萌新失望啦。切入正题。似乎在初学自动机相关的内容时，许多人难以建立对自动机的初步印象，尤其是在自学的时侯。而这篇文章就是为你们打造的。笔者在自学AC自动机后花费两天时间制作若干的gif，呈现出一个相对直观的自动机形态。尽管这个图似乎不太可读，但这绝对是在作者自学的时侯，画得最~~妙不可读~~的gif了。另外有些小伙伴问这个gif拿什么画的。笔者名誉担保：用Windows画图。
+我知道，很多人在第一次看到这个东西的时侯是非常兴奋的。（别问我为什么知道）不过这个自动机啊它叫作`Automaton`，不是`Automation`，让萌新失望啦。切入正题。似乎在初学自动机相关的内容时，许多人难以建立对自动机的初步印象，尤其是在自学的时侯。而这篇文章就是为你们打造的。笔者在自学 AC 自动机后花费两天时间制作若干的 gif，呈现出一个相对直观的自动机形态。尽管这个图似乎不太可读，但这绝对是在作者自学的时侯，画得最~~妙不可读~~的 gif 了。另外有些小伙伴问这个 gif 拿什么画的。笔者用 Windows 画图软件制作。
 
 ## 概述
 
@@ -12,17 +12,17 @@ AC 自动机是**以 TRIE 的结构为基础**，结合**KMP 的思想**建立
 
 ## 字典树构建
 
-AC自动机在初始时会将若干个模式串丢到一个TRIE里，然后在TRIE上建立AC自动机。这个TRIE就是普通的TRIE，该怎么建怎么建。
+AC 自动机在初始时会将若干个模式串丢到一个 TRIE 里，然后在 TRIE 上建立 AC 自动机。这个 TRIE 就是普通的 TRIE，该怎么建怎么建。
 
-这里需要仔细解释一下 TRIE 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。TRIE中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，TRIE的边就是状态的转移。
+这里需要仔细解释一下 TRIE 的结点的含义，尽管这很小儿科，但在之后的理解中极其重要。TRIE 中的结点表示的是某个模式串的前缀。我们在后文也将其称作状态。一个结点表示一个状态，TRIE 的边就是状态的转移。
 
-形式化地说，对于若干个模式串$s_1,s_2\dots s_n$，将它们构建一棵字典树后的所有状态的集合记作 $Q$。
+形式化地说，对于若干个模式串 $s_1,s_2\dots s_n$，将它们构建一棵字典树后的所有状态的集合记作 $Q$。
 
 ## 失配指针
 
-AC自动机利用一个fail指针来辅助多模式串的匹配。
+AC 自动机利用一个 fail 指针来辅助多模式串的匹配。
 
-状态 $u$ 的 fail 指针指向另一个状态 $v$ ，其中 $v\in Q$ ，且 $v$ 是 $u$ 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。对于学过KMP的朋友，我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：
+状态 $u$ 的 fail 指针指向另一个状态 $v$ ，其中 $v\in Q$ ，且 $v$ 是 $u$ 的最长后缀（即在若干个后缀状态中取最长的一个作为 fail 指针）。对于学过 KMP 的朋友，我在这里简单对比一下这里的 fail 指针与 KMP 中的 next 指针：
 
 1. 共同点：两者同样是在失配的时候用于跳转的指针。
 2. 不同点：next 指针求的是最长 Border（即最长的相同前后缀），而 fail 指针指向所有模式串的前缀中匹配当前状态的最长后缀。
@@ -68,11 +68,11 @@ AC 自动机在做匹配时，同一位上可匹配多个模式串。
 
 ## 字典树与字典图
 
-我们直接上代码吧。字典树插入的代码就不分析了（后面完整代码里有），先来看构建函数 `build()`，该函数的目标有两个，一个是构建fail指针，一个是构建自动机。参数如下：
+我们直接上代码吧。字典树插入的代码就不分析了（后面完整代码里有），先来看构建函数 `build()`，该函数的目标有两个，一个是构建 fail 指针，一个是构建自动机。参数如下：
 
 1. `tr[u,c]` 这个有两者理解方式。我们可以简单理解为字典树上的一条边，即 $trie[u,c]$；也可以理解为从状态（结点） $u$ 后加一个字符`c`到达的状态（结点），即一个状态转移函数 $trans(u,c)$。下文中我们将用第二种理解方式继续讲解。
-2. `q` 队列，用于BFS遍历字典树。
-3. `fail[u]` 结点 $u$ 的fail指针。
+2. `q` 队列，用于 BFS 遍历字典树。
+3. `fail[u]` 结点 $u$ 的 fail 指针。
 
 ```cpp
 void build(){
@@ -95,9 +95,9 @@ void build(){
 
 接下来解答一下上文提出的问题。细心的同学会发现，`else ` 语句的代码会修改字典树的结构。没错，它将不存在的字典树的状态链接到了失配指针的对应状态。在原字典树中，每一个结点代表一个字符串 $S$，是某个模式串的前缀。而在修改字典树结构后，尽管增加了许多转移关系，但结点（状态）所代表的字符串是不变的。
 
-而 $trans(S,c)$ 相当于是在 $S$ 后添加一个字符 `c` 变成另一个状态 $S'$。如果$S'$存在，说明存在一个模式串的前缀是$S'$，否则我们让 $trans(S,c)$ 指向 $trans(fail[S],c)$。由于$fail[S]$ 对应的字符串是$S$ 的后缀，因此$trans(fail[S],c)$ 对应的字符串也是 $S'$ 的后缀。
+而 $trans(S,c)$ 相当于是在 $S$ 后添加一个字符 `c` 变成另一个状态 $S'$。如果 $S'$ 存在，说明存在一个模式串的前缀是 $S'$，否则我们让 $trans(S,c)$ 指向 $trans(fail[S],c)$。由于 $fail[S]$ 对应的字符串是 $S$ 的后缀，因此 $trans(fail[S],c)$ 对应的字符串也是 $S'$ 的后缀。
 
-换言之在 TRIE 上跳转的时侯，我们只会从 $S$ 跳转到 $S'$，相当于匹配了一个 $S'$；但在AC自动机上跳转的时侯，我们会从$S$跳转到$S'$的后缀，也就是说我们匹配一个字符 `c`，然后舍弃 $S$ 的部分前缀。舍弃前缀显然是能匹配的。那么fail指针呢？它也是在舍弃前缀啊！试想一下，如果文本串能匹配$S$ ，显然它也能匹配 $S$ 的后缀。所谓的 fail 指针其实就是 $S$ 的一个后缀集合。
+换言之在 TRIE 上跳转的时侯，我们只会从 $S$ 跳转到 $S'$，相当于匹配了一个 $S'$；但在 AC 自动机上跳转的时侯，我们会从 $S$ 跳转到 $S'$ 的后缀，也就是说我们匹配一个字符 `c`，然后舍弃 $S$ 的部分前缀。舍弃前缀显然是能匹配的。那么 fail 指针呢？它也是在舍弃前缀啊！试想一下，如果文本串能匹配 $S$ ，显然它也能匹配 $S$ 的后缀。所谓的 fail 指针其实就是 $S$ 的一个后缀集合。
 
 这样修改字典树的结构，使得匹配转移更加完善。同时它将 fail 指针跳转的路径做了压缩（就像并查集的路径压缩），使得本来需要跳很多次 fail 指针变成跳一次。
 
@@ -106,17 +106,17 @@ void build(){
 ![AC_automation_gif_b_pro3.gif](./images/ac-automaton2.gif)
 
 1. 蓝色结点： BFS 遍历到的结点 u
-2. 蓝色的边：当前结点下，AC自动机修改字典树结构连出的边。
-3. 黑色的边：AC自动机修改字典树结构连出的边。
-4. 红色的边：当前结点求出的fail指针
-5. 黄色的边：fail指针
+2. 蓝色的边：当前结点下，AC 自动机修改字典树结构连出的边。
+3. 黑色的边：AC 自动机修改字典树结构连出的边。
+4. 红色的边：当前结点求出的 fail 指针
+5. 黄色的边：fail 指针
 6. 灰色的边：字典树的边
 
-可以发现，众多交错的黑色边将字典树变成了**字典图**。图中省s略了连向根结点的黑边（否则会更乱）。我们重点分析一下结点 5 遍历时的情况，~~再妙不可读也请大家硬着头皮去读~~。我们求 $trans(5,\text{ s })=6$ 的 fail 指针：
+可以发现，众多交错的黑色边将字典树变成了**字典图**。图中省 s 略了连向根结点的黑边（否则会更乱）。我们重点分析一下结点 5 遍历时的情况，~~再妙不可读也请大家硬着头皮去读~~。我们求 $trans(5,\text{ s })=6$ 的 fail 指针：
 
 ![AC_automation_b_7.png](./images/ac-automaton2.png)
 
-本来的策略是找fail指针，于是我们跳到 $fail[5]=10$发现没有 `s` 连出的字典树的边，于是跳到 $fail[10]=0$ ，发现有$trie[0,\text{ s }]=7$，于是$fail[6]=7$；但是有了黑边、蓝边，我们跳到 $fail[5]=10$ 之后直接走 $trans(10,\text{ s })=7$ 就走到$7$号结点了。~~其实我知道没人会仔细看这鬼扯的两张图片的QAQ~~
+本来的策略是找 fail 指针，于是我们跳到 $fail[5]=10$ 发现没有 `s` 连出的字典树的边，于是跳到 $fail[10]=0$ ，发现有 $trie[0,\text{ s }]=7$，于是 $fail[6]=7$；但是有了黑边、蓝边，我们跳到 $fail[5]=10$ 之后直接走 $trans(10,\text{ s })=7$ 就走到 $7$ 号结点了。~~其实我知道没人会仔细看这鬼扯的两张图片的 QAQ~~
 
 这就是 build 完成的两件事：构建 fail 指针和建立字典图。这个字典图也会在查询的时候起到关键作用。
 
@@ -136,7 +136,7 @@ int query(char *t){
     return res;
 }
 ```
-声明 $u$ 作为字典树上当前匹配到的结点，$res$ 即返回的答案。循环遍历匹配串，$u$ 在字典树上跟踪当前字符。利用 fail 指针找出所有匹配的模式串，累加到答案中。然后清 0。对 $e[j]$ 取反的操作用来判断 $e[j]$ 是否等于 -1。在上文中我们分析过，字典树的结构其实就是一个 $trans$ 函数，而构建好这个函数后，在匹配字符串的过程中，我们会舍弃部分前缀达到最低限度的匹配。fail指针则指向了更多的匹配状态。最后上一份图。对于刚才的自动机：
+声明 $u$ 作为字典树上当前匹配到的结点，$res$ 即返回的答案。循环遍历匹配串，$u$ 在字典树上跟踪当前字符。利用 fail 指针找出所有匹配的模式串，累加到答案中。然后清 0。对 $e[j]$ 取反的操作用来判断 $e[j]$ 是否等于 -1。在上文中我们分析过，字典树的结构其实就是一个 $trans$ 函数，而构建好这个函数后，在匹配字符串的过程中，我们会舍弃部分前缀达到最低限度的匹配。fail 指针则指向了更多的匹配状态。最后上一份图。对于刚才的自动机：
 
 ![AC_automation_b_13.png](./images/ac-automaton3.png)
 
@@ -151,11 +151,11 @@ int query(char *t){
 
 ## 总结
 
-~~希望~~大家看懂了文章。其实总结一下，你只需要知道AC自动机的板子很好背就行啦。
+~~希望~~大家看懂了文章。其实总结一下，你只需要知道 AC 自动机的板子很好背就行啦。
 
-???+ note "模板1"
+???+ note "模板 1"
 
-    [LuoguP3808【模板】AC 自动机（简单版）](https://www.luogu.org/problemnew/show/P3808) 
+    [LuoguP3808【模板】AC 自动机（简单版）](https://www.luogu.org/problemnew/show/P3808)
 
     ```cpp
     #include<bits/stdc++.h>
@@ -208,7 +208,7 @@ int query(char *t){
     }
     ```
 
-???+ note "模板2"
+???+ note "模板 2"
 
     [P3796 【模板】AC 自动机（加强版）](https://www.luogu.org/problemnew/show/P3796)
 
@@ -285,7 +285,7 @@ KMP 自动机：一个不断读入待匹配串，每次匹配时走到接受状
 
 共有 $m$ 个状态，第 $i$ 个状态表示已经匹配了前 $i$ 个字符。
 
-定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态， $next_{i}$ 表示[prefix function](/string/prefix-function)，则有：
+定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态， $next_{i}$ 表示 [prefix function](/string/prefix-function)，则有：
 
 $$
 trans_{i,c} =
@@ -297,7 +297,7 @@ $$
 
 （约定 $next_{0}=0$ ）
 
-我们发现 $trans_{i}$ 只依赖于之前的值，所以可以跟[KMP](/string/prefix-function/##knuth-morris-pratt)一起求出来。
+我们发现 $trans_{i}$ 只依赖于之前的值，所以可以跟 [KMP](/string/prefix-function/##knuth-morris-pratt) 一起求出来。
 
 时间和空间复杂度： $O(m|\Sigma|)$。
 
-- 
2.11.0