AC自动机入门详解+例题 hdu2222
首先简要介绍一下AC自动机:Aho-Corasick automation,该算法在1975年产生于贝尔实验室,是著名的多模匹配算法之一。一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。要搞懂AC自动机,先得有字典树Trie和KMP模式匹配算法的基础知识。KMP算法是单模式串的字符匹配算法,AC自动机是多模式串的字符匹配算法。
因为AC自动机算法是建立在字典树的基础上,如果不太了解字典树,就先自行普及一下字典树,这里和KMP算法相似的地方是因为这儿每个字典树节点中都要包含一个fail域,表示当前这个节点失配后要从fail节点开始匹配。
下面以she he say shr her为单词以yasherhs为文本串来匹配。可以画出下图
图中虚线部分表示每个节点的fail指针的指向。
下边具体看一下fail指针的求法
fail指针用BFS来求得,对于直接与根节点相连的节点来说,如果这些节点失配,他们的Fail指针直接指向root即可,其他节点其Fail指针求法如下:
假设当前节点为father,其孩子节点记为child。求child的Fail指针时,首先我们要找到其father的Fail指针所指向的节点,假如是t的话,我们就要看t的孩子中有没有和child节点所表示的字母相同的节点,如果有的话,这个节点就是child的fail指针,如果发现没有,则需要找father->fail->fail这个节点,然后重复上面过程,如果一直找都找不到,则child的fail指针就要指向root。
下边我们来看一下fail指针的具体用法,在匹配过程中有两种情况;
(1)当前字符匹配,表示从当前节点沿着树边有一条路径可以到达目标字符,如果当前匹配的字符是一个单词的结尾,我们可以沿着当前字符的fail指针,一直遍历到根,如果这些节点末尾有标记(此处标记代表,节点是一个单词末尾的标记),这些节点全都是可以匹配上的节点。我们统计完毕后,并将那些节点标记。此时只需沿该路径走向下一个节点继续匹配即可,目标字符串指针移向下个字符继续匹配;
(2)当前字符不匹配,则去当前节点失败指针所指向的字符继续匹配,匹配过程随着指针指向root结束。重复这2个过程中的任意一个,直到模式串走到结尾为止。
具体代码如下:
#include <bits/stdc++.h>
using namespace std;
struct Trie///节点类型
{
Trie *fail;
Trie *child[26];
int is_str;
Trie()///构造函数完成每个节点的初始化
{
is_str = 0;
fail = NULL;
for(int i=0;i<26;i++){
child[i] = NULL;
}
}
};
Trie *root,*temp,*current;
char str[10000005],key[55];
int head,tail;
void _insert(char s[])///插入构造字典树
{
current = root;
for(int i=0;i<strlen(s);i++){
int index = s[i]-'a';
if(current->child[index] == NULL){
temp = new Trie;
current->child[index] = temp;
}
current = current->child[index];
}
current->is_str++;///标记一下根节点到这个节点表示一个单词
}
void Find_fail()///寻找失配指针
{
queue<Trie*> Q;
Q.push(root);
Trie *p;
while(!Q.empty()){
temp = new Trie;
temp = Q.front();Q.pop();
for(int i=0;i<26;i++){
if(temp->child[i]!=NULL){
if(temp == root)
temp->child[i]->fail = root;///根节点的孩子节点的失配指针指向根节点
else{
p = temp ->fail;///用一个指针p暂时保存当前节点的失配指针,首先等于他父亲节点的失配指针
while(p){///从它父亲节点的失配指针开始找起,如果能找到一个和它相同的节点,这个节点就是当前节点的失配指针
if(p->child[i]!=NULL){
temp ->child[i] ->fail = p->child[i];
break;
}
p = p->fail;
}
if(p == NULL) temp->child[i]->fail = root;///如果找到根节点的失配指针还没有找到与它相同的节点,则这个节点的失配指针就是根节点
}
Q.push(temp->child[i]);
}
}
}
}
int sum;
void AC_automation(char s[])
{
current = root;
int len = strlen(s);
for(int i=0;i<len;i++){
int index = s[i] - 'a';
while(!current->child[index]&¤t != root)///如果这个字符不存在,就找它的失配指针,直到找到失配指针为止
current = current -> fail;
current = current->child[index];
if(!current) current = root;///看看失配指针的下一个字符是否存在,如若不存在就从失配指针开始找
temp = current;
while(temp != root)///一直从失配指针找下去,因为从根节点到每个适配指针,表示从根结点到这个节点表示字符串的后缀
{
if(temp->is_str>=0){///如果这个节点没有被找过就给它加上一次,因为不是单词,加上0,对结果没有影响
sum += temp->is_str;
temp->is_str = -1;///加上之后要标记一下
}
else break;///否则就直接结束
temp = temp->fail;
}
}
}
int main()
{
int T;scanf("%d",&T);
while(T--){
int n;
root = new Trie;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",key);
_insert(key);
}
Find_fail();
sum = 0;
scanf("%s",str);
AC_automation(str);
printf("%d\n",sum);
}
return 0;
}
下一篇: 通俗易懂のAC自动机小结