AC自动机详细讲解

约定不等于承诺〃 2022-11-08 05:56 145阅读 0赞

AC自动机简介：

首先简要介绍一下AC自动机：Aho-Corasickautomation，该算法在1975年产生于贝尔实验室，  
是著名的多模匹配算法之一。一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，  
让你找出有多少个单词在文章里出现过。要搞懂AC自动机，先得有字典树Trie和KMP模式匹配算法的  
基础知识。KMP算法是单模式串的字符匹配算法，AC自动机是多模式串的字符匹配算法。  
此AC和平时刷题的AC可不一样，AC自动机不自动AC编程题。  
个人觉得AC自动机根字典树的联系比较大，但是和KMP的联系并不大。

字典树Trie：  
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，  
排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的  
优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。  
简而言之：字典树就是像平时使用的字典一样的，我们把所有的单词编排入一个字典里面，当我们  
查找单词的时候，我们首先看单词首字母，进入首字母所再的树枝，然后看第二个字母，再进入相应的树枝，  
假如该单词再字典树中存在，那么我们只用花费单词长度的时间查询到这个单词。

字典树的构建过程：  
当前给出n个字符串，我们用这n个字符串来构建字典树，构建的过程是这样的，按顺序将n个字符串插入  
到字典树，插入某个单词的时候，我们遍历这个字符串，如果发现当前要插入的字符其节点在先前已经建成，  
我们直接取考虑下一个字符即可。当我们发现当前要插入的字符对应的节点还没有创建，我们就创建一个新的  
节点。往下处理其他字符，重复上述过程。

例如一个例子she,he,say,her,shr构建字典树的形态如下动图所示。

其中绿色节点代表从根节点到当前节点所组成的字符串是一个完整的单词。我们对其标记一下。

字典树的构建代码：非完全版  
/\*动态链表写法\*/  
const int maxn = 26;  
typedef struct TrieNode ///字典树节点定义  
\{  
bool isWord; ///标记是否是完整的单词  
struct TrieNode \*son\[maxn\]; ///26个儿子。  
\}Trie;  
void insertWord(Trie \*root,char word\[\]) ///将单词word插入到字典树  
\{  
Trie \*p = root;  
int i = 0;  
char ch = word\[i\];  
while(ch != '\\0')  
\{  
if(p->son\[ch-'a'\] == NULL) ///节点不存在创造节点  
\{  
Trie \*node = (Trie\*)malloc(sizeof(Trie));  
for(int i = 0; i < maxn; i++)  
\{  
node->son\[i\] = NULL;  
\}  
node->isWord = false;  
p->son\[ch-'a'\] = node;  
p = p->son\[ch-'a'\];  
\}  
else ///节点已经存在，直接到下一个节点  
\{  
p = p->son\[ch-'a'\];  
\}  
ch = word\[++i\];  
\}  
p->isWord = true; ///单词插入完毕后，进行标记  
\}  
  
  
/\*\*静态链表做法\*\*/  
const int maxn = 26;  
struct TrieNode  
\{  
bool isWord;  
struct TrieNode \*son\[maxn\];  
\}node\[100000\];  
int num;  
TrieNode\* createNode()  
\{  
TrieNode \*p = &node\[num++\];  
for(int i = 0; i < maxn; i++)  
\{  
p->son\[i\] = NULL;  
\}  
return p;  
\}  
void insertTel(TrieNode \*root,char word\[\])  
\{  
TrieNode \*p;  
p = root;  
int i = 0;  
char ch = word\[i\];  
while(ch != '\\0')  
\{  
if(p->son\[ch-'a'\] == NULL)  
\{  
  
p->son\[ch-'a'\] = createNode();  
p = p->son\[ch-'a'\];  
p->isWord = false;  
\}  
else  
\{  
p = p->son\[ch-'a'\];  
\}  
ch = tel\[++i\];  
\}  
p->isWord = true;  
\}

以上两个代码是构建字典树的代码：  
一个是动态链表一个是静态链表写的，动态链表写的时候就是动态分配内存，有点就是用多少节点创建  
多少节点，缺点，分配内存时比较耗时，有时候会超时，静态链表写法优点就是比较快，但是会消耗大量的  
内存，用不用反正我都开了那么多。

AC自动机第一关键点创建字典树：

AC自动机作为多模式匹配，假如有n个模式串，一个长为m的文本串，让找有多少个模式串在文本串中  
出现过，我们首先要做的第一步就是用n个模式串建立字典树，上面我们已经讲解了如何创建字典树，因此  
我们对n个模式串she,he,say,her,shr已经可以创建出上图的字典树。

AC自动机第二关键点找节点的Fail指针构建AC自动机：

在KMP算法中，当我们比较到一个字符发现失配的时候，我们会通过next数组找到下一个开始匹配的位置，  
然后进行字符串的匹配操作，当然我们知道KMP算法适用于单模式匹配，所谓单模式匹配就是给出一个模式串，  
给出一个文本串，然后看模式串在文本串中第一次出现的位置。  
在AC自动机中，我们也有类似next数组的东西就是fail指针，当发现失配的时候，跳转到fail指针指向的位置，  
然后再次进行匹配操作，AC自动机之所以能够实现多模式串与文本串的匹配，就归功于fail指针的建立，也就是fail  
指针的建立，我们这颗树才变成了AC自动机，否则其就是一颗单纯的字典树。  
fail指针的建立是通过广搜（BFS）来实现的，其节点搜索的顺序与树的层次遍历是完全相同。对于直接与  
根相连的节点来说，这些节点的fail指针直接指向root(根节点).其他节点的fail指针求法如下。假设当前节点为  
father，它已经求过fail指针了，如果father出队,我们现在就要求father节点孩子们的失败指针。对于那些非空  
的孩子节点，由于他们存在，所以我们要求他们的fail指针，对于father下面为空的孩子节点，我们不予理睬就  
可以了。对于father节点的非空孩子t,t必然代表了一个字母，此时我们首先找到father->fail。然后看看  
father->fail->child 有没有等于和t表示的字符是一样的，如果有的话t->fail = father->fail->child。如果发现  
没有的话，我们继续往前翻找，father->fail->fail->child有没有和t表示的字符一样的孩子，有的话  
t->fail = father->fail->fail->child。否则的话继续往前翻找，翻找到什么程度，如果都翻到根了，还没找到  
对应的节点的话，则我们只能让t->fail指向根节点了。  
下图是各个节点的fail指针的指向：

图中最后一个yasherhs是文本串。  
我们按照广搜的思路来走一下。最开始的时候根节点root进队。  
1.root出队，我们为root的儿子们找fail指针，通过检测我们发现当前是要给root的儿子们h,s找fail，指针，  
股h,s直接指向root，如图中红色虚线所示。并且h,s依次进队。当前队列中有h,s  
2.接下来h出队，我们现在要给h的儿子e找fail指针，因此首先我们temp = h->fail，我们知道temp现在肯定  
是root,然后会看root的孩子有没有字符是e的，发现是没有的，这时候已经到根了，没有办法往前再翻找了，所以  
节点e的fail指针就指向了root。同时e进队。当前队列有s,e  
3.接下来出队的是s,我们现在要给s的儿子a,h找fail指针，按照顺序先给a找，同样temp = s->fail，则temp现在  
指向根节点root,我们发现根节点的孩子是没有字符是a的，所以a的fail只能指向root.同时a进队，此时队列有e,a。然后找h的fail指针，同样temp = s->fail，则temp依然是根，我们发现根节点的孩子有字符是h的，则这个时候h的  
fail指针就会指向第二层的h节点。然后h进队，当前队列e a h.第三层的节点的fail指针就都找完了，如图中蓝色虚线  
所示。  
4.接下来出队的e,然后该给e的孩子r找fail指针，同样temp = e->fail。则temp是根root当前，我们看根节点  
下面没有字符是r的节点,所以r的fail会指向root,r进队，当前队里面有 a , h , r.  
5.接下来出队的a,然后找a的孩子y的fail指针，可以发现情况和4这一条是相同的，所以y的fail指针也是指向  
root的。同时y进队。当前队里面有h,r,y  
6.接下来h出队，我们给h的孩子e,r找fail指针，按顺序先给e找，temp = h->fail。则当前temp就是第二层的  
h，然后我们看temp的孩子有没有是字符e的，发现第二层的h其孩子有字符值是e的.则e的fail指针就指向图中第  
三层的e,同时e进队，然后我们找r的fail，会发现r其情况与4，5是相同的，则r的fail指针指向root.并且r进队。  
当前队中节点有：r,y,e,r。 第四层的所有点的fail指针已经找到，其指向如图中绿色虚线线条所示。  
7.r出队，找r的孩子的fail指针，发现r没有孩子，那就不管了，后面的y,e,r都是没孩子的，依次出队就可以  
了。  
此时我们已经给字典树上各个节点求了fail指针，所以AC自动机已构建完毕。

求Fail指针的代码片段：  
///求fail指针。构造AC自动机。  
void build\_AC\_automaton()  
\{  
TrieNode \*p;  
p = root;  
queue<TrieNode\*>qu;  
qu.push(p);  
while(!qu.empty())  
\{  
p = qu.front();  
qu.pop();  
for(int i = 0; i < allSon; i++)  
\{  
if(p->son\[i\] != NULL) ///第i个孩子存在  
\{  
if(p == root) ///p是根，根节点的孩子的失败指针都指向自己  
\{  
p->son\[i\]->fail = root;  
\}  
else  
\{  
TrieNode \*node = p->fail;  
while(node != NULL)  
\{  
if(node->son\[i\]!=NULL)  
\{  
p->son\[i\]->fail = node->son\[i\];  
break;  
\}  
node = node->fail;  
\}  
if(node == NULL)  
p->son\[i\]->fail = root;  
\}  
qu.push(p->son\[i\]);  
\}  
\}  
\}  
\}

AC自动机第三关键点文本串的匹配：

最后一步就是让文本串上AC自动机上跑一遍。匹配的过程分了两种情况。  
（1）当前节点node与文本串上字符成功匹配，我们要做的是检测当前节点是否有标记表示它是模式串  
中一个单词的结尾，如果是结尾的话，就说明当前节点到根这条路上字母组成的单词是一个完整的单词，  
我们统计的单词数就要加1.不管它是不是结尾我们都要执行下面的操作，此时我们可以利用当前节点的fail指针，  
找到另一个节点temp=node->fail。如果发现它也有标记表明它是一个完整的单词，则我们就可以让统计的单词  
数加1.That's why。因为temp=node->fail。从temp这个节点到root所组成的字符串是从node到root所组成字符  
串的后缀，你肯定又到问That's why。然而这点还是要从fail指针的求解过程中找答案。首先我们知道一点，node  
和 node->fail这两个节点代表的字符是相同的。（除非节点的fail指针是root）现在有节点father我们给其孩子  
child找fail指针，首先找到father的fail指针记为fail\_father，然后看fail\_father的孩子有没有和child所代表的字符  
相同的。有的话我们记这个节点为fail\_child。则child->fail = fail\_child。father和fail\_father所代表字符相同，  
child和fail\_child所代表的字符相同。则他们的关系如图所示：

同样的道理，father节点和它的父亲也是按上面的方法给father找fail指针的。所以当前node节点匹配上了  
文本串的一个字符，记root到node的字符串用\[root,node\]来表示，则我们可以通过temp= node->fail.则根据上面的讲解，\[root,temp\] 是 \[root,node\]的后缀，如果发现当前节点temp有标记，则说明\[root,temp\]也是一个完整的单词，要统计上，temp = temp->fail.\[root,temp\]又是上一个\[root,temp\]的后缀，如果它也是一个完整单词，则也要统计。直到翻找到根节点我们就不用找了。这就是AC自动机，不会露掉一个串。  
（2）如果当前节点node匹配上了文本串的一个字符，然后发现匹配下一个字符的时候是失配的，那么我们  
就到node->fail处，因为【root,node->fail】是【root,node】的后缀，我们知道【root,node->fail】这一段还是  
根文本串中的一段是匹配着的，我们看node->fail它的孩子有没有给我失配的字符匹配得上得，匹配不上得话，  
就要往前翻找node->fail->fail。如果配上了的话，我们执行（1）,否则就往前找。一直进行这个过程。

还是这个图，我们用文本串yasherhs在AC自动机上跑一次，我们直接用眼观察得话，就可以知道her,he,she  
这些模式串在yasherhs中出现过，则答案就就是3，现在我们跑依次来看看对不对。  
首先现在匹配y,看root的孩子有没有y，发现没有，则root就会找自己的fail指针，发现是空的，也就是说匹配  
下一次匹配要从root开始开始进入，然后遍历到a,发现root的孩子也没有a,那么root找自己的fail指针，是空，下次  
配的时候还要从root开始，然后遍历到s,我们发现root的孩子有s，则此时字符s得到匹配，然后通过temp指针一直  
翻找s对应的fail，因为那些后缀可能是完整的单词，统计过后是0. 执行完操作（1）直接往下匹配，遍历到字符h,  
发现s的孩子有h，则此时字符sh都得到匹配，同时temp翻找h的fail，统计出来也是0.然后往下匹配，遍历到字符e，发现h的孩子有e,则此时字符she都得到匹配，检测到e是一个完整单词的结尾，统计单词数+1.同时找e->fail，找到了第二层的e，当前这个节点代表的单词是she的后缀he ，而且发现第二层的e是个完整单词的结尾，则统计单词数加+1,然后第二层的e还会去找fail，发现到root了.则翻找过程结束，当前匹配到的单词数是2.然后我们继续遍历文本串，该遍历r，原来是匹配了she,现在第四层e的孩子没有r，则r当前失配,找e的失败指针，找到了第三层的e，代表后缀he,我们发现e后面有r,则r也匹配上了，则现在匹配到的是her，发现r是一个完整的单词，统计+1，然后temp来翻找那  
些后缀是不是完整的单词。发现没有。接下来遍历到文本串的h发现第四层r下面没有h，发现h失配，那么就找h->fail  
发现是根,根下面有是h的孩子，则就从第二层的h开始匹配上了，然后我们遍历到文本串的最后一个字符，s发现第二  
层h后面没有s这个节点，则s失配了，就找h->fail，是根，发现根下面有s这个字符，则s和第一层的s配上了，然而  
这个s不是任何单词的结尾，此时匹配结束。我们统计到5个模式串有3个在文本串中出现过。

PS：在此讲解中，我一直说节点代表字母，这样是不准确的，确切说一个节点有两层含义，第一层：代表根  
root到当前节点node的字符串，第二层，代表该字符串的最后一个字符。

AC自动机完整的模板代码如下：  
\#include <iostream>  
\#include <stdio.h>  
\#include <stdlib.h>  
\#include <queue>  
  
using namespace std;  
  
const int allSon=26;  
char patten\[60\]; ///模式串  
char text\[1000010\]; ///文本串  
int ans;  
struct TrieNode  
\{  
struct TrieNode \*son\[allSon\]; ///儿子们  
struct TrieNode \*fail; ///匹配失败时候的指针指向  
int num; ///以该节点所代表字符串为结尾的单词数  
\}\*root;  
///创建节点  
TrieNode\* createNode()  
\{  
TrieNode \*p;  
p = (TrieNode\*)malloc(sizeof(TrieNode));  
for(int i = 0; i < allSon; i++) p->son\[i\] = NULL;  
p->num = 0;  
p->fail = NULL;  
return p;  
\}  
///插入模式串，构建字典树  
void insertPatten()  
\{  
TrieNode \*p;  
p = root;  
int index = 0;  
while(patten\[index\] != '\\0')  
\{  
int lowercase = patten\[index\]-'a';  
if(p->son\[lowercase\]==NULL)  
\{  
p->son\[lowercase\] = createNode();  
\}  
p = p->son\[lowercase\];  
index++;  
\}  
p->num++;  
\}  
///求fail指针。构造AC自动机。  
void build\_AC\_automaton()  
\{  
TrieNode \*p;  
p = root;  
queue<TrieNode\*>qu;  
qu.push(p);  
while(!qu.empty())  
\{  
p = qu.front();  
qu.pop();  
for(int i = 0; i < allSon; i++)  
\{  
if(p->son\[i\] != NULL) ///第i个孩子存在  
\{  
if(p == root) ///p是根，根节点的孩子的失败指针都指向自己  
\{  
p->son\[i\]->fail = root;  
\}  
else  
\{  
TrieNode \*node = p->fail;  
while(node != NULL)  
\{  
if(node->son\[i\]!=NULL)  
\{  
p->son\[i\]->fail = node->son\[i\];  
break;  
\}  
node = node->fail;  
\}  
if(node == NULL)  
p->son\[i\]->fail = root;  
\}  
qu.push(p->son\[i\]);  
\}  
\}  
\}  
\}  
void find\_in\_AC\_automaton()  
\{  
TrieNode \*p;  
p = root;  
int index = 0;  
while(text\[index\] != '\\0')  
\{  
int lowercase = text\[index\]-'a';  
while(p->son\[lowercase\]==NULL && p!=root)  
p = p->fail; ///失配，转到能配的地方再尝试匹配  
p = p->son\[lowercase\];  
if(p == NULL) p = root;  
TrieNode \*temp = p; ///把那些以当前节点的后缀作为后缀的字符串统计了。  
while(temp!=NULL && temp->num!=-1)  
\{  
ans += temp->num;  
temp->num = -1;  
temp = temp->fail;  
\}  
index++;  
\}  
\}  
///记得释放接内存，用完及时归还系统，不然会爆的。  
void freeNode(TrieNode \*node)  
\{  
if(node != NULL)  
\{  
for(int i = 0; i < allSon; i++)  
freeNode(node->son\[i\]);  
\}  
free(node);  
\}  
int main()  
\{  
int t,n;  
scanf("%d",&t);  
while(t--)  
\{  
scanf("%d",&n);  
root = createNode();  
for(int i = 0; i < n; i++)  
\{  
scanf("%s",patten);  
insertPatten(); ///用模式串构建字典树  
\}  
scanf("%s",text);  
build\_AC\_automaton(); ///构建AC自动机  
ans = 0;  
find\_in\_AC\_automaton(); ///多模式匹配  
printf("%d\\n",ans);  
freeNode(root); ///释放内存  
\}  
return 0;  
\}

如有错误请及时告知，必将改正，以免误认子弟。  
如要转载请留言告知，转载博客必附原文链接。  
————————————————  
版权声明：本文为CSDN博主「温姑娘」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/wyxeainn/article/details/77430218