AC自动机主要思想

单模匹配的时候,我们往往可以运用kmp算法来进行匹配,时间复杂度相当可观。不过,在多模匹配时,kmp算法就显得力不从心。所以在1975年,贝尔实验室才产生了Aho-Corasick automation,AC自动机这种算法。

讲讲kmp

大家在学AC自动机之前一定知道kmp算法,以及其时间复杂度:O(m+n)。为什么怎么快?因为失匹配不是一步天涯,而是退后仅仅几步。AC自动机紧紧围绕这个特点进行操作。这也是AC自动机的优点之一。

讲讲Trie

Trie就是大家熟悉的字典树,它的结构就是AC自动机的主体。如果还不知道Trie的不用慌,blog,仔细看一看,主要看一看实现一段。

Trie的单词插入,查找,为字符串的一系列算法提供了强大作用。

回归AC自动机

AC自动机并不是Accepted自动机,而是一种数据结构,一种算法。我们来主要讲一讲思想。

我们可以用kmp来后悔,同样也可以在Trie上后悔。我们可以建立Fail指针,当我们在Trie上匹配失败的时候,就可以转到fail指针上,然后继续匹配。这样子也就大大减少了时间复杂度,并且思路及其简单。

但是有时候我们想不通如何匹配,我们建Trie的是匹配串而不是被匹配串。其实我们对一个root的子节点一直搜到树的底部,一旦失配,立即转向fail指针就可以了。同理,如果匹配到底面了,同样可以走fail指针。所以就说AC自动机是kmp+Trie,名不虚传。

那么我们只剩一个问题了:如何建立fail指针?

首先,根节点的fail指针可以连向自己,也可以连向一个”假点”,node[0]。然后我们按照Bfs序来搜索。
但我们搜索到点u的时候,看一看它的父亲fail的点,然后看它有没有连向一个点v,并且边的char(string等等)是否更u的父亲到它的边的char一样。
如果一样,说明这个点可以成为u的fail指针连向点,同时也是最优(唯一?)的fail点。下面的ppt有非常详细的过程,可以参观orz…

某一个Dalao的ppt链接,可以参考。