AC自动机

概述

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


Trie树

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

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

下面看一个例子:
trie.jpg
其中,红色的节点表示该字符是其所在字符串的结束字符(也就是最后一个字符)。我们会发现结束字符不一定非是叶子节点,也可能是内部节点。
如果两个字符串拥有相同的前缀,那么对于这个前缀而言,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:dehde
模式串2:acdea

对应的Trie树是:
fail.png
其中,虚线表示fail指针,未画fail指针的节点的fail指针指向根节点。
构建fail指针的过程,也不是很复杂:
首先根节点的孩子节点的fail指针指向根节点。然后在广度优先遍历的过程中,为每个节点设置fail指针。如果节点N的父节点P的fail指针指向节点F,并且F的某个孩子Q所包含的字符 和 节点N所包含的字符相同,那么N的fail指针指向Q,否则指向根节点。

2,如何构建output表

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

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

代码实现

tim-chow的github

感谢浏览tim chow的作品!

如果您喜欢,可以分享到: 更多

如果您有任何疑问或想要与tim chow进行交流

可点此给tim chow发信

如有问题,也可在下面留言: