前言
先看一道题目：题面
这是一道十分典型的 AC自动机 的题目，需要运用 AC自动机 和 矩阵乘法 解决
part 1
什么叫 AC自动机
AC 自动机，顾名思义，就是 帮助我们自动 \color{green}{AC} 的机器 一个高效地解决字符串匹配问题的算法，全称是 Aho-Corasick Automaton。
引入
当你在玩王者荣耀/蛋仔派对的时候，你的操作像人机一样，就会发现你的聊天窗口会有 **** 的队友问候，为什么会出现 **** 呢？这是因为游戏后台的字符串匹配算法在发力。
part 2
实现方法
第一步，建立Tire树
加上我们现在有一个原串和敏感词汇如下：
| 原串 | 敏感词汇 |
|---|---|
| caofkoktiiit | cao |
| ^ | ao |
| ^ | fk |
| ^ | it |
那么我们先建立字典树：
然后给每个敏感词汇的最后一个字母标记上此敏感词汇的长度，方便回溯（绿色表示当前敏感词汇的最后一个节点）：
第二步，建立Fail指针
- root节点的Fail指针指向自己
- 非root节点的Fail指针有两个选择
1.如果他的父节点的Fail指针指向的节点下方的孩子节点（只能是直接的孩子节点，孩子节点的孩子节点不行）有与此节点相同的节点，此节点的Fail指针指向这个节点（与此节点相同的节点）
2.否则，此节点的Fail指针指向root节点
那么给字典树建立Fail指针：
第三步，匹配
原串：caofkoktiiit
开始匹配
1.c 走到root下面的c节点，不是结束节点，继续遍历
2.a 走到c下面的a节点，不是结束节点，继续遍历
3.o 走到a下面的o节点，是结束节点，结束遍历，并回溯3位和2位，分别得到：\color{red}{cao} 和 \color{red}{ao} 且传送至o节点的Fail指针指向的节点root
4.f 走到root下面的f节点，不是结束节点，继续遍历
5.k 走到f下面的k节点，是结束节点，结束遍历，并回溯2位，得到：\color{red}{fk} 且传送至k节点的Fail指针指向的节点root
6.o 走到root下面的o节点，但没有此节点，继续遍历
7.k 走到root下面的k节点，但没有此节点，继续遍历
8.t 走到root下面的t节点，但没有此节点，继续遍历
9.i 走到root下面的i节点，不是结束节点，继续遍历
10.i 走到i下面的i节点，但没有此节点，继续遍历
11.i 走到i下面的i节点，但没有此节点，继续遍历
12.t 走到i下面的t节点，是结束节点，结束遍历，并回溯2位，得到：\color{red}{it} 且传送至k节点的Fail指针指向的节点root
13.无，结束遍历。得到了答案：\color{red}{cao} 、 \color{red}{ao} 、 \color{red}{fk} 和 \color{red}{it}
part 3
后记
终于写完了，AC自动机的代码实现就请大家自己去琢磨了，再见！！
