大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46，售后保障稳定
学习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]);
}
}
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/223028.html原文链接：https://javaforall.net
