2.3 Aho-Corasick自动机
Aho-Corasick自动机（AC自动机）算法在1975年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，找出有多少个单词在文章里出现过。要理解AC自动机，先得有Trie树（字典树）和KMP算法的基础知识。AC自动机算法分为3步：构造一棵Trie树，构造失败指针（fail指针），以及模式匹配过程。
2.3.1 Aho-Corasick自动机原理
以典型应用为例，现给定3个单词“china”“hit”“use”，再给定一段文本“chitchat”，求有多少个单词出现在文本中。
（1）根据单词集合{china,hit,use}建立一棵Trie树，如图2.4所示。
图2.4 建立Trie树
（2）根据所给文本“chitchat”依次匹配，图中所示“chi”为匹配成功的字符串，如图2.5所示。
图2.5 匹配成功的字符串
（3）当匹配到第四个字符时，“t”和“n”匹配失败，如图2.6所示。
图2.6 匹配失败
（4）此时知道已匹配成功的字符串为“chi”。
AC算法的核心就是在所有给定的单词中，找到这样的一个单词，使其与已匹配成功字符串的相同前后缀最长，利用这个最长的相同前后缀实现搜索跳转。例如，单词“hit”与已匹配成功字符串“chi”的最长相同前后缀为“hi”，因此下一步从单词“hit”的“t”开始搜索，如图2.7所示。
图2.7 搜索跳转
（5）此时“t”是匹配的，在文本“chitchat”中找到一个单词“hit”。
其实到这里，AC算法的思想已经基本呈现在读者面前了。剩下的问题就是如何解决所述的“核心”。
AC算法的关键：在每个节点里设置一个指针（称之为fail指针），指向跳转的位置。
对于跳转位置的选择，基于以下两点：
（1）对于根节点的所有子节点，它们的fail指针都指向根节点；
（2）而对于其他节点，不妨设该节点上的字符为“ch”，沿着它的父节点的fail指针走，直到走到一个节点，它的子节点中也有字符为“ch”的节点，然后把该节点的fail指针指向那个字符为“ch”的节点。如果一直走到根节点都没找到，则把fail指针指向根节点。
指针跳转如图2.8所示。
图2.8 指针跳转
2.3.2 Aho-Corasick自动机算法的实现
2.3.3 例题讲解
例2-3 Keywords Search
Time Limit:2000/1000 ms（Java/Others） Memory Limit:131072/131072 KB（Java/Others）
题目描述：
给定n个单词以及1个字符串，问字符串中出现了多少个单词（如单词“her”“he”为字符串“aher”中出现了两个单词）。
输入：
第一行输入测试数据的组数，然后输入一个整数n（n≤10000），在接下来的n行中每行输入一个单词（每个单词都只包含“a”～“z”，并且单词长度不超过50），最后输入一个字符串（长度不超过1000000）。
输出：
对于每组数据，要输出一行，包含一个整数，该整数表示在字符串中出现了多少个单词。
样例输入：
1
5
she
he
say
shr
her
yasherhs
样例输出：
3
题目来源：HDU 2222。
解题思路：
经典的模板题。
