AC 自动机知识

1. AC 自动机简介

AC 自动机（Aho-Corasick Automaton）：该算法在 1975 年产生于贝尔实验室，是最著名的多模式匹配算法之一。简单来说，AC 自动机是以 字典树（Trie） 的结构为基础，结合 KMP 算法思想 建立的。

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

1. 构造一棵字典树（Trie），作为 AC 自动机的搜索数据结构。
2. 利用 KMP 算法思想，构造失配指针。使得当前字符失配时可以通过失配指针跳转到具有最长公共前后缀的字符位置上继续匹配。
3. 扫描文本串进行匹配。

2. AC 自动机原理

接下来我们以一个例子来说明一下 AC 自动机的原理。

描述：给定 5 个单词，分别是 say、she、shr、he、her，再给定一个文本串 yasherhs。

要求：计算出有多少个单词在文本串中出现过。

2.1 构造一棵字典树（Trie）

首先我们需要建立一棵字典树。

2.2 构造失配指针

2.3 扫描文本串

3. AC 自动机的应用