AC. 梦想

frank_c1

AC自动机和Fail树

发布于2015年11月22日 | 暂无评论 | 5,227阅读 | AC自动机,字符串

一直对AC自动机有种执念,觉得有它就能自动AC,是种特别神奇的算法,今天终于见识了。实际上,学习了AC自动机以后,才发现并没有那么玄乎。
 
一、Trie(字典树/前缀树)

学习AC自动机前,需要学会字典树。字典树,顾名思义当然是一棵树。特殊地,这棵树上的边是字符。那么对于任意一条从起点到某一结点的路径,都对应唯一的字符串。这样我们就可以用字典树上的结点来表示字符串。

如图,路径0-1经过“a",那么结点1就对应字符串“a";路径0-1-2-3依次经过“a","b","c",那么结点3就对应字符串"abc";路径0-1-4-5依次经过"a","a","a",那么结点5就对应字符串"aaa"……

从中我们可以发现,某一结点对应的字符串其实就是从结点0到该结点路径上的字符顺次连接而成的串。

在字典树上我们可以方便地实现字符串的插入、查找。

对于树上的结点,我们可以保存一些附加信息。如果我们规定结点的权值,用非零值表示单词结点,我们就可以用一棵字典树表示出一个由字符串组成的集合,并完成一些有用的工作,比如词频统计、前缀匹配等。

 
二、KMP算法(单模式匹配)

KMP算法是一个著名的单模式匹配算法,由三个发现者D.E.Knuth,J.H.Morris和V.R.Pratt的名字命名。

如果真的要用一篇文章来叙述KMP算法的思想,估计10多页的论文都说不完。这真是一个十分优美而又简洁的算法,虽然有点难于理解,但若是深入了解它的工作过程,一定会惊叹于它的精妙绝伦。

朴素算法进行单模式匹配,最坏情况下复杂度是O(nm);而KMP算法是O(n+m)。是什么大大加速了匹配过程?核心之处在于失配指针。朴素的方法之所以复杂度较高,在于它做了许多没有必要的比较。试想一下,如果模板串“abbababb"已经匹配到“abbabab"了,只有最后一个字符不一样,那我们要全部重新来过吗?

不用,既然已经匹配了“abbabab",那么前面两个字符一定是“ab",只要继续匹配模板串的第三个字符就好了。

如图是失配时的状态转移图,其中虚线箭头就是所谓的失配指针。当匹配某一字符失败时,只要转移到失配指针指向处继续匹配即可。具体的算法过程不再赘述,附上代码一份:

 
三、AC自动机(多模式匹配)

观察下图,如果我们把虚线箭头全部去掉,其实就是第一部分中的Trie;而那些虚线箭头,貌似是第二部分中的失配指针?

Trie+失配指针,就基本上组成了传说中的AC自动机。AC自动机,由其发现者Aho Corasick的名字命名,用于解决多模式匹配的问题。

可以说,AC自动机就是KMP算法以Trie为基础的实现。其中失配指针的作用也和KMP算法中的一样,写法也类似。唯一有些不同的是,在单模式匹配中,由于只有一个模板串,成功匹配也就是一个串;但是多模式匹配时,有可能在成功匹配一个模板串时,也同时成功匹配了另一个模板串。这个问题可以用后缀链接进行处理。

 
四、优化:Trie图

注意到,在AC自动机匹配时,每一步可能有多次回溯(直到找到一个可以继续匹配的结点)。那么我们是否可以在之前就完成一些工作,使每步只需要转移一次呢?

我们引入Trie图的概念。Trie图是一个确定性有限状态自动机(DFA),比起AC自动机,增加了确定性的属性。即在任一位置,输入任一字符集中的字符,都可以转移到一个确定的结点。

实现方法很简单,就是把getFail()中的 if(!u) continue;  改成 if(!u) {ch[k][c]=ch[f[k]][c];continue;}  ,然后就可以把Find()中 while(u && !ch[u][c]) u=f[u]; 删去。实质上就是通过添加有向边,使所有的转移统一化。这样做的直接好处就是在AC自动机上动规时转移比较方便。
 
五、拓展:Fail树

例题:[BZOJ 3172] 单词