题意:给出一些单词，求多少个单词在字符串中出现过（单词表单词可能有相同的,这些相同的单词视为不同的分别计数）（如果单词x在字符串中出现一次而在单词表中有两个则ans+2,在字符串中出现两次而单词表中有一个则ans+1）
AC自动机模板题，之前学了总觉得不扎实，现在有底了现在终于可以去敲心头大恨，兴奋！！！
代码
#include<cstdio>
#include<cstring>
const int maxn=;
const double eps=1e-;
const long long modn=;
int n;
char a[]={};
char b[*maxn]={};
struct trie{
int next[];
bool exist;
int count;
int fail;
}e[maxn*]={};
int tot,ans;
int q[maxn*]={}; void init(int x,int k,int j){
if(j>k){
e[x].exist=;
e[x].count++;
return;
}
int z=a[j]-'a';
if(!e[x].next[z])
e[x].next[z]=++tot;
init(e[x].next[z],k,j+);
}
void fir(){
memset(e,,sizeof(e)); memset(q,,sizeof(q));
tot=ans=;
}
void doit(){
int head=,tail=,x,y,f;
q[]=;
while(head<=tail){
x=q[head++];
for(int i=;i<;i++){
if(e[x].next[i]){
y=e[x].next[i];
if(x!=){
f=e[x].fail;
while((!e[f].next[i]) && f )
f=e[f].fail;
e[y].fail=e[f].next[i];
}q[++tail]=y;
}
}
}
}
void find(){
scanf("%s",&b);
int k=std::strlen(b);
int x=,z,y;
for(int i=;i<k;i++){
z=b[i]-'a';
while( (!e[x].next[z])&& x){
x=e[x].fail;
}x=e[x].next[z]; y=x;
while(y&&e[y].count){
ans+=e[y].count;
e[y].count=;
y=e[y].fail;
}
}
}
int main(){
int T;scanf("%d",&T);
while(T-->){
fir();
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",&a);
init(,std::strlen(a)-,);
}
doit();
find();
printf("%d\n",ans);
}
return ;
}
更新：
整理模板的时候发现自己原来的代码有问题。这个新版本应该没问题了。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int maxn=;
int n,siz;
char ch[]={};
char str[maxn*]={};
struct trie{
int sig[];
int cnt;
int vis;
int fail;
}t[maxn*];int tot=;
int q[maxn*]={};int head=,tail=;
void fir(){
tot=;memset(t,,sizeof(t));//memset(q,0,sizeof(q));
}
void init(int x,int j){
if(j>siz-){ t[x].cnt++; return; }
int z=ch[j]-'a';
if(!t[x].sig[z])t[x].sig[z]=++tot;
init(t[x].sig[z],j+);
}
void build_fail(){
int head=,tail=,x,y,f;q[]=;
while(head<=tail){
x=q[head++];
for(int i=;i<;i++)
if(t[x].sig[i]){
y=t[x].sig[i];
if(x){
f=t[x].fail;
while((!t[f].sig[i])&&f)
f=t[f].fail;
t[y].fail=t[f].sig[i];
}q[++tail]=y;
}
}
}
int get_num(){//字符串中包含的单词数量，重复的不记录，
//如果单词x在字符串中出现一次而在单词表中有两个则ans+2
//在字符串中出现两次而单词表中有一个则ans+1
int ans=,x=,y,z;
for(int i=;i<siz;i++){
z=str[i]-'a';
while((!t[x].sig[z])&&x)
x=t[x].fail;
x=t[x].sig[z];y=x;
while(y&&(!t[y].vis)){//保证了每个结尾只访问一次
ans+=t[y].cnt;
t[y].vis=;t[y].cnt=;
y=t[y].fail;
}
}
return ans;
}
int main(){
int T;scanf("%d",&T);
while(T-->){
fir();
scanf("%d",&n);
for(int i=;i<=n;i++){scanf("%s",ch);siz=strlen(ch);init(,);}
build_fail();
scanf("%s",str);siz=strlen(str);
printf("%d\n",get_num());
}
return ;
}
new