概述

AC 自动机用于多模式匹配。AC 自动机建立在 Trie 树和 KMP 算法的基础之上。关于 KMP 算法可以参考 http://timd.cn/kmp。下面的内容将先介绍 Trie 树,然后再介绍 AC 自动机。


Trie树

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

下面看一个例子:

trie.jpg

其中红色节点表示该字符是其所在字符串的结束字符,结束字符不一定是叶子节点,也可能是内部节点。

如果两个字符串拥有相同的前缀,那么对于该前缀而言,Trie 树只会存储一次,这就是 Trie 树节省存储空间的原理。


AC 自动机

AC 自动机有三要素:

其中 goto 表是一棵 Trie 树;fail 表是在 Trie 树中加上失败指针。因此 AC 自动机是一棵加了失败指针的 Trie 树。

1,fail 指针是什么

fail 指针相当于 KMP 算法中的 next 数组。当匹配失败时,会从 fail 指针所指向的节点处继续匹配。

任意节点 N 所表示的字符串的后缀可能是其它模式串的前缀,表示最长的那个后缀所对应的模式串前缀的节点就是 N 的 fail 指针指向的节点,比如:

模式串1:ashe

模式串2:sha

模式串3:he

对应的 Trie 树是:

fail.png

其中,虚线表示 fail 指针,未画 fail 指针的节点的 fail 指针指向 root。

在广度优先遍历的过程中,为每个节点的孩子节点设置 fail 指针:

1, 根节点的 fail 指针是 null;根节点的孩子节点的 fail 指针指向根节点

2,对于其它任意节点 N,设其父节点为 P,F = P.fail

  2.1,如果 F 的某个孩子节点 Q 包含的字符与 N 包含的字符相同,则 N.fail = Q,然后退出

  2.2,否则,令 F = F.fail,然后回到步骤 2.1,直到 F = null

2,如何构建output表

对于某个节点 P,其 output 表的计算方式是:

while (P != null) {
    if (P 是其所在的模式串的终结字符)
        输出 P;
    P = P.fail;
}

Python 实现

tim-chow 的 Github