欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - HDU2222
题意概括
先给出一些模式串，然后给出一个母串，统计先前给出的模式串中，有多少个在母串中出现。多组数据。
题解
AC自动机模板题。
首先根据输入数据构建AC自动机。
然后对于每一位，沿着fail指针走，全部统计并累加。
有一个小小的优化，就是走过的都标记为-1，下次碰到-1就不走了。因为如果这个节点的标记为-1，那么它的fail一再在它之前就标记成-1了（即统计过了）。
代码
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=10005,L1=55,L2=1000005;
int T,n,cnt;
char ch[L1],str[L2];
struct Trie{
int e,fail,Next[26];
void init(){
e=fail=0;
memset(Next,0,sizeof Next);
}
}tree[N*L1];
void AC_init(){
cnt=1;
tree[0].init();
tree[1].init();
for (int i=0;i<26;i++)
tree[0].Next[i]=1;
}
void build(char ch[]){
int rt=1,t,len=strlen(ch);
for (int i=0;i<len;i++){
t=ch[i]-'a';
if (!tree[rt].Next[t]){
tree[++cnt].init();
tree[rt].Next[t]=cnt;
}
rt=tree[rt].Next[t];
}
tree[rt].e++;
}
int q[N*L1],head,tail;
void build_AC(){
int rt,k,son;
head=tail=0;
tree[0].fail=1,tree[1].fail=0;
q[++tail]=1;
while (head<tail){
rt=q[++head];
for (int i=0;i<26;i++){
son=tree[rt].Next[i];
if (!son){
tree[rt].Next[i]=tree[tree[rt].fail].Next[i];
continue;
}
k=tree[rt].fail;
while (!tree[k].Next[i])
k=tree[k].fail;
tree[son].fail=tree[k].Next[i];
q[++tail]=son;
}
}
}
int solve(){
int rt=1,t,len=strlen(str);
int ans=0;
for (int i=0;i<len;i++){
t=str[i]-'a';
rt=tree[rt].Next[t];
int k=rt;
while (~tree[k].e){
ans+=tree[k].e;
tree[k].e=-1;
k=tree[k].fail;
}
}
return ans;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
AC_init();
for (int i=0;i<n;i++){
scanf("%s",ch);
build(ch);
}
build_AC();
scanf("%s",str);
printf("%d
",solve());
}
return 0;
}