AC 自动机_模式匹配自动机

学习AC自动机的前提是要会trie数和KMP字符串匹配， 它的功能是能对好多个模式串进行同时查找。

比如对4个模式串：

he

hers

his

she

在一条母串中：shejjjjj 查找每个模式串出现的次数.

我们知道KMP算法有个next数组，和KMP类似，AC自动机有一个fail指针数组，用来对整棵trie树进行滚动。

AC 自动机：

HUD 3065：

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int ch[1002*52][26],End[1002*52],cur,fail[1002*52],last[1002*52],ans[1002];

char str[2000005],str0[1002][52];

void get_fail() {

int now,tmpFail,Next;

queue<int> q;

//用bfs生成fail

//初始化队列

for(int j=0;j<26;j++) {

if(ch[0][j]) {

q.push(ch[0][j]);

fail[ch[0][j]] = 0;

last[ch[0][j]] = 0;

}

}

while(!q.empty()) {

//从队列中拿出now

//此时now中的fail、last已经算好了

//下面计算的是ch[now][j]中的fail、last。

now = q.front();q.pop();

for(int j=0;j<26;j++) {

if(!ch[now][j]) continue;

Next = ch[now][j];

q.push(Next);

tmpFail = fail[now];//kjkhj

while(tmpFail&&!ch[tmpFail][j]) tmpFail = fail[tmpFail];

fail[Next] = ch[tmpFail][j];

last[Next] = End[fail[Next]] ? fail[Next]:last[fail[Next]];

}

}

}

void Find(){

int now = 0;

int len = strlen(str);

for(int i=0;i<len;i++){

if(str[i]<‘A’||str[i]>’Z’) {now=0;continue;}

str[i]-=’A’;

while(now&&!ch[now][str[i]]) now = fail[now];

now = ch[now][str[i]];

if(End[now]) ans[End[now]]++;

int tmp = now;

//重要理解

//这时候已经滚到了节点now，下面就需要找出所有以now为结尾的模式串，就需要用到last数组了。Last数组保存的是以节点now为结尾的模式串。

//比如 abcd bcd 两个模式串，abcd中d节点的last指向bcd中的d节点。

//当然两个d节点不是同一个。

//这样就能知道当滚到abcd的d节点时，我们还同时找到了bcd这个串。

//如果存在，在找到abcd的同时，我们还找到了bcd cd d 这三个模式串。

//事实上，下面last数组滚过的结点，在之前可能从来没有被访问过。

//《训练指南》上的代码找的是包含模式串的一段母字符串，而不是找出所有出现过的模式串。

while(last[tmp]) {

ans[End[last[tmp]]]++;

tmp = last[tmp];

}

}

}

int main(){

int n,now;

while(scanf(“%d”,&n)!=EOF){

memset(ch,0,sizeof(ch));

memset(End,0,sizeof(End));

memset(ans,0,sizeof(ans));

memset(last,0,sizeof(last));

cur = 1;

int len;

for(int i=1;i<=n;i++) {

scanf(“%s”,str0[i]);

len = strlen(str0[i]);

now = 0;

for(int j=0;j<len;j++) {

str0[i][j]-=’A’;

if(ch[now][str0[i][j]]==0) ch[now][str0[i][j]] = cur++;

now = ch[now][str0[i][j]];

str0[i][j]+=’A’;

}

End[now] = i;

}

get_fail();

scanf(“%s”,str);

Find();

for(int i=1;i<=n;i++) {

if(ans[i])

printf(“%s: %d\n”,str0[i],ans[i]);

}

}

}

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

发布者：全栈程序员-用户IM，转载请注明出处：https://javaforall.cn/223028.html原文链接：https://javaforall.cn