AC 自动机用于多模式匹配。AC 自动机建立在 Trie 树和 KMP 算法的基础之上。关于 KMP 算法可以参考 http://timd.cn/kmp。下面的内容将先介绍 Trie 树,然后再介绍 AC 自动机。
Trie 树也叫字典树。它满足如下性质:
下面看一个例子:
其中红色节点表示该字符是其所在字符串的结束字符,结束字符不一定是叶子节点,也可能是内部节点。
如果两个字符串拥有相同的前缀,那么对于该前缀而言,Trie 树只会存储一次,这就是 Trie 树节省存储空间的原理。
AC 自动机有三要素:
q = goto(p, v)
表示在状态 p 时,输入字符 v,会转移到状态 q,因此 goto 是一个有限状态机q = fail(v)
表示在 goto 匹配失败时,会转移到状态 qoutput(p)
表示在到达状态 p 时,哪些模式串匹配成功其中 goto 表是一棵 Trie 树;fail 表是在 Trie 树中加上失败指针。因此 AC 自动机是一棵加了失败指针的 Trie 树。
1,fail 指针是什么
fail 指针相当于 KMP 算法中的 next 数组。当匹配失败时,会从 fail 指针所指向的节点处继续匹配。
任意节点 N 所表示的字符串的后缀可能是其它模式串的前缀,表示最长的那个后缀所对应的模式串前缀的节点就是 N 的 fail 指针指向的节点,比如:
模式串1:ashe
模式串2:sha
模式串3:he
对应的 Trie 树是:
其中,虚线表示 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; }