ac自动机学习

缘起

继续和字符串算法刚. ac自动机是过不去的坎~

分析

Aho-Corasick 算法,又叫做AC自动机。是一种多模式串匹配算法。

AC自动机算法=trie树+kmp.

ac自动机可以在目标串查找多个模式串，出现次数以及出现的位置。

AC自动机主要是应用有限自动机的状态转移来模拟字符的比较

一个常见的例子就是给出n个单词（n个模式串），再给出一段包含m个字符的文章（文本串），让你找出有多少个单词（模式串）在文章（文本串）里出现过。

本文就以这种场景作为例子介绍ac自动机. 即

1
2
3
给定5个单词：say she shr he her，
然后给定一篇文章 yasherhs。 额~ 文章有点短小哈
问一共有多少单词在这篇文章中出现过。

其实我想说一句~，如果你把【1】中的kmp 理解透了的话, ac自动机是秒懂的. 至少，我看ac自动机第一眼就懂了. 不就是将kmp的next思想引入模式串构成的trie树上——使得trie树变成trie图了吗? ac自动机就是这么简单!!!

好了，言归正传~ 我们来讲一下ac自动机是怎么构造的

  1. 使用模式串构建标准trie. 这没什么好说的, 具体参见【2】
  2. 使用bfs构建trie上每个节点的fail指针. 其中A节点上的fail指针指向trie上的B节点的含义是如果在A的孩子处失配了, 则要跳到B节点上去, 看看B节点的孩子中有木有当前的text[i]的.

关于第二点不好懂? 不急，首先我们说，其实fail指针的引入破坏了trie树的树的结构的（树无圈，树是DAG）， 所以有些文章将ac自动机又称为trie图. 例如本文中的那5个单词构建的ac自动机（trie图）就长下面的样子

上面的箭头就是fail指针. 关于第二点，我们对比kmp和ac自动机来看

  1. kmp中的next指针的含义是, next[a]=k的含义是如果在pattern[a]失配（即pattern[a]!=text[i]）的话, 则应该跳到pattern[k]继续和text[i]进行比较. 而k保证了pattern[1,….,k-1]和pattern[a-k+1,…,a-1]相等，而且k具有满足这种相等的最大性质. 其中最大性质的目的是使得保证不会漏掉匹配.
  2. ac自动机中的fail指针的含义是, fail[A]=B的含义是如果在A的任何一个孩子（注意, A在trie中，所以要谈及它的孩子节点）中找不到text[i], 即失配了. 则要跳到B节点去, 看看B是否有一个孩子是text[i], 亦即 B.next[text[i]-‘a’]不是空指针. 而且要保证B节点代表的前缀（因为trie的另一个名称就是前缀树）和A代表的前缀的某个后缀相等. 并且保证这种相等的长度的最大性（这也是为了防止漏掉匹配）.

仔细看看~ 其实他喵的不就是一回事吗? A不就是kmp中的a-1吗? B不就是kmp中的k-1吗? 他们的孩子节点不就是kmp中的a和k吗? 因为kmp是单模式串的匹配，而ac自动机是多模式串的匹配. 所以如果仅仅只有一个模式串的话, ac自动机将蜕化为kmp算法. 所以不夸张的说——ac自动机可以用于解决kmp问题.

原理搞清楚了，那么如何构造ac自动机的fail指针呢? 用bfs! 此话怎讲? 其实就是用它的父节点的fail指针来构造当前节点的fail指针! 假设我们已经得到了父节点的fail指针，即p1,p2,..,pk,e, 其中pk是e的父节点. pk指向q1,…,qr的qr, 那么我们考虑e的fail指针应该指向谁? pk的fail指针指向qr的含义就是前缀q1,…,qr和前缀p1,..,pk的某个后缀完全相等, 并且保证这种相等的长度的最大性. 那么e的fail指针指向哪里? 假设指向f， 其实就是保证 前缀p1,…,pk,e的某个后缀和一个前缀P完全一样. 并且保证这种相等的最大性. 那么我们自然先找到qr（即fail[pk]）,然后看qr.next[e-‘a’]有木有（其中e代表的字符我们依旧简记e），如果有的话, 则显然fail[e]=qr.next[e-‘a’]，如果木有的话，则继续用fail[qr]跳. 直至跳到某个节点K，它要么是trie的root（跳不动了），要么满足K.next[e-‘a’]存在. 则fail[e]=K. 归纳法保证这样找到的满足相等的最大性. 其实你想想就知道为什么可以这样了? 其实和【1】中的后面那段意识流的论述是一样的.

一图胜千言

至于ac自动机的代码, 参见 【3】.

其实你去看【1】中的makenext方法, 和这里讲的bfs制作fail指针简直是一模一样~

ac自动机的fail指针和kmp的next数组唯一的区别在于, kmp的next数组是在孩子节点上的, 而ac自动机的fail指针是在父节点上的. 这是因为ac自动机的父节点可能有不止一个孩子（因为ac自动机是多串匹配啊~），所以不好把fail指针放在孩子节点上面。而kmp只有一个后继（就是数组索引后继）, 所以放在孩子节点上是方便的.

参考

【1】https://yfsyfs.github.io/2019/06/17/%E5%AD%97%E7%AC%A6%E4%B8%B2%E5%8C%B9%E9%85%8D%E7%AE%97%E6%B3%95%E4%B9%8Bkmp/

【2】https://yfsyfs.github.io/2019/07/21/hdu-1251-%E7%BB%9F%E8%AE%A1%E9%9A%BE%E9%A2%98-trie/

【3】https://yfsyfs.github.io/2019/10/13/hdu-2222-Keywords-Search-ac%E8%87%AA%E5%8A%A8%E6%9C%BA%E6%9D%BF%E9%A2%98/