AC自动机详解

前言

先看一道题目：题面

这是一道十分典型的 AC自动机 的题目，需要运用 AC自动机 和 矩阵乘法 解决

part 1

什么叫 AC自动机

AC 自动机，顾名思义，就是 帮助我们自动 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位，分别得到：cao 和 ao 且传送至o节点的Fail指针指向的节点root

4.f 走到root下面的f节点，不是结束节点，继续遍历

5.k 走到f下面的k节点，是结束节点，结束遍历，并回溯2位，得到：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位，得到：it 且传送至k节点的Fail指针指向的节点root

13.无，结束遍历。得到了答案：cao 、 ao 、 fk 和 it

part 3

后记

终于写完了，AC自动机的代码实现就请大家自己去琢磨了，再见！！