参考博文：AC自动机算法详解 （转载） （原文作者：DarkRaven，原文的链接失效了）
图片来源：AC自动机算法详解 （转载）
主要内容：
- 什么是AC自动机
- AC自动机用来做什么
- 前置知识
- 算法分析
- 代码实现
什么是AC自动机
Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。要学会AC自动机，我们必须知道什么是Trie，也就是字典树。Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
(来源：百度百科)
- 所以AC自动机不是Accept automaton，是Aho-Corasick automaton，并不能帮你自动AC。
用来做什么？
AC自动机针对是多模式串匹配问题。例：给几个关键词（模式串），再给一篇文章，判断关键词是否在文章中出现，或出现的次数。
前置知识
- 必须掌握：trie树
- 建议掌握：KMP算法
AC自动机的工作原理就是将模式串构建成一个trie树(字典树)，然后对目标串进行匹配。其中构建trie树的关键在于，当失配(匹配失败)的时候，匹配转向失配节点的失败节点(或称转换节点)。构建trie树是AC自动机的关键，而失配的处理和kmp的处理思想相同，整体的算法思想也是将模式串先处理。所以建议掌握kmp算法，再进行AC自动机的学习。
算法分析
-
AC自动机的三个过程：
1.插入模式串 构建Trie树
2.设置失败节点
3.对目标串进行匹配
1. 构建Trie树
正常的构建过程，每插入一个模式串对每个字符进行遍历，如果节点不存在就创建，继续向下层拓展。（结尾的节点需要特殊标志）
假设模式串有：she , he ,say, her, shr
我们要构建一棵字典树：
2.设置失败节点
设置失败节点是AC自动机的关键所在，在KMP算法中失败数组，指向的是失配之后继续匹配的位置，最终的效果就是对目标串扫描一遍，不需要回溯。而KMP中找的是最长公共前后缀。AC自动机找的是父节点的失败节点的子节点。
我们定义
struct {
Node* father //父节点
Node* fail //失败节点
Node* children[26] //孩子节点
}Node
注：该代码为了理解，与实际节点有所不同
我们通过bfs遍历节点，每个节点处理完毕后，孩子入队，直到队列为空。
一般情况：
假设当前节点为p，那么我们需要找到p->father ->fail ->child，查看child是否有与p节点字母相同的节点，若有 p->fail = p->father->fail->children[与p相同]，若无我们要寻找p->father->fail->fail，直到找到与p对应的child节点或达到root节点。
第一层节点：
p->fail = root;
(实际的代码编写中，并不需要设置父节点的指针，可以认为p是父节点，对他的children节点进行遍历设置，操作将会是p->children[i]->fail = p->fail->children)
失败节点的正确性：失败节点的特点是与原节点的字母相同，那么我们找到父节点的失败节点，找到的节点与原节点的父节点相同。那么父节点的失败节点(p_father->fail)找的是父节点的父节点(p_father->father)，这样以此类推，查找的路径都将是正确的。
-
一个例子
首先我们将root入队。
- 第一层（fail为红色虚线）：
root出队，遍历root所有的子节点h，s使之fail指向root，并且将h，s入队。 - 第二层（fail为蓝色虚线）：
h出队，找到e，找到h节点的失败节点root，root节点下无e节点，因为节点为root，e的fail指向root，e入队。
s出队，找到a，找到s节点的失败节点root，root节点下无a节点，因为节点为root，a的fail指向root，a入队。找到h，找到s节点的失败节点root，root下有h节点，第三层的h节点的fail指向root节点的子节点h。h入队。 - 第三层（fail为绿色虚线）：
对目标串进行匹配
从root节点开始
-
目标串匹配的两种情况：
- 对应字符子节点存在：
a. 为结尾节点，计数后，对该节点进行一次fail节点遍历到root，并对每个fail节点计（这次遍历不影响当前匹配节点）
b. 不为结尾节点，寻找子节点是否有下一个字符 - 对应字符子节点不存在
a. 该节点不是root节点，寻找该节点的fail节点
b. 该节点是root节点，寻找子节点是否有下一个字符
不断重复以上过程，遍历直到完目标串。
- 对应字符子节点存在：
-
一个例子
这是上面我们已经构造好的AC自动机
我们现在用目标串：yasherhs进行匹配，设匹配节点p，初始节点p=root，当i=0,1时匹配不成功。p依旧指向root。
当i=2，3，4时，p节点匹配路径为she，p指向了第三层的e节点，计数一次(1)，现在构建临时的一个temp节点，temp=p,去找temp->fail，发现temp->fail也为结尾，计数一次(2)。继续找temp->fail->fail,找到root结束。继续遍历目标串。
当i=5时，继续寻找p节点的子节点，没找到r节点，p=p->fail，我们找到了第三层的e节点，找到子节点r，p=r，r为结尾节点，计数一次(3)。
当i=6时，未找到h子节点，p回到了r->fail节点root。
当i=7时，找到h节点但并不是结尾节点。i=8回到root。结束。 -
我们能发现最后成功匹配的三次，在匹配的时候对具体代码进行调整，也实现每个模式串只匹配一次，记录匹配成功的串等操作。
经典的AC自动机是判断模式串出现的个数，因此在每次成功的时候会对节点进行已访问的标记。
代码实现
经典AC自动机
代码来自源AC自动机算法详解 （转载）
- 基本数据结构
const int kind = 26;
struct node
{
node *fail; //失败指针
node *next[kind]; //Tire每个节点的个子节点（最多个字母）
int count; //是否为该单词的最后一个节点
node() //构造函数初始化
{
fail=NULL;
count=0;
memset(next,NULL,sizeof(next));
}
}*q[500001]; //队列，方便用于bfs构造失败指针
char keyword[51]; //输入的单词
char str[1000001]; //模式串
int head,tail; //队列的头尾指针
- 构建trie树
void insert(char *str,node *root){
node *p=root;
int i=0,index;
while(str[i])
{
index=str[i]-'a';
if(p->next[index]==NULL) p->next[index]=new node();
p=p->next[index];
i++;
}
p->count++; //在单词的最后一个节点count+1，代表一个单词
}
- 设置失败节点
void build_ac_automation(node *root){
int i;
root->fail=NULL;
q[head++]=root;
while(head!=tail)
{
node *temp=q[tail++];
node *p=NULL;
for(i=0; i<26; i++)
{
if(temp->next[i]!=NULL)
{
if(temp==root) temp->next[i]->fail=root;
else
{
p=temp->fail;
while(p!=NULL)
{
if(p->next[i]!=NULL)
{
temp->next[i]->fail=p->next[i];
break;
}
p=p->fail;
}
if(p==NULL) temp->next[i]->fail=root;
}
q[head++]=temp->next[i];
}
}
}
}
- 目标串匹配
int query(node *root){
int i=0,cnt=0,index,len=strlen(str);
node *p=root;
while(str[i])
{
index=str[i]-'a';
while(p->next[index]==NULL && p!=root) p=p->fail;
p=p->next[index];
p=(p==NULL)?root:p;
node *temp=p;
while(temp!=root && temp->count!=-1)
{
cnt+=temp->count;
temp->count=-1;
temp=temp->fail;
}
i++;
}
return cnt;
}
网友评论