概述

AC自动机是进行多模式匹配的。可以认为AC自动机是建立在Trie树和KMP算法基础上的。关于KMP算法可以参考这篇文档，下面会先介绍下Trie树，然后深入介绍AC自动机。

Trie树

Trie树也叫字典树。它满足如下的性质：

• 除根节点外，每个节点都只包含一个字符
• 每个节点的所有子节点包含的字符都是不同的
• 从根节点到某个节点，路径上所经过的字符，就是该节点代表的字符串

下面看一个例子：

其中，红色的节点表示该字符是其所在字符串的结束字符（也就是最后一个字符）。我们会发现结束字符不一定非是叶子节点，也可能是内部节点。
如果两个字符串拥有相同的前缀，那么对于这个前缀而言，Trie树只会存储一次，这也是Trie树节省存储空间的原理。

AC自动机

AC自动机有三要素：

• goto表
  q = goto(p, v)表示在状态p时，输入字符v，会转移到q状态，因此goto其实是一个有限状态机
• fail表
  q = fail(v)表示在goto匹配失败时，会转移到状态q
• output表
  output(p)表示在到达状态p时，哪些模式串匹配成功了

其中，goto表其实就是一棵Trie树，而fail表则是在Trie树中加上失败指针，总而言之，AC自动机其实就是一棵加了失败指针的Trie树。

1，fail指针是什么

fail指针相当于KMP算法中的next数组。当匹配失败时，会从fail指针所指向的节点处继续进行匹配。
如果某个节点所表示的字符串的某个后缀 是 某个模式串的前缀，那么这些后缀中长度最长的那个后缀 所对应的模式串的前缀所对应的节点，就是该节点的fail指针所指向的节点。比如：

模式串1：ashe
模式串2：sha
模式串3：he

对应的Trie树是：

其中，虚线表示fail指针，未画fail指针的节点的fail指针都指向root。
构建fail指针的过程，也不是很复杂：
在广度优先遍历的过程中，为每个节点的孩子节点设置fail指针：

1. 根节点的fail指针是null；根节点的孩子节点的fail指针都指向根节点
2. 对其他的节点N而言，设其父节点为P，F = P.fail
3. 如果F的某个孩子节点Q包含的字符 与 N包含的字符相同，则N.fail = Q；
4. 否则，令F = F.fail，重复执行步骤3，一直到F为null

ch = N.getCharacter();
F = P.fail;
while (F != null) {
    if ((Q = F.getNode(ch)) != null) {
        N.fail = Q;
        break;
    }
    F = F.fail;
}

2，如何构建output表

对于某个节点P，其output列表的计算方式是：

while (P != null) {
    if (P是其所在的某个模式串的终结字符)
        输出P
    P = P的fail指针所指向的节点
}

代码实现

tim-chow的github