AC自动机（优化版）
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5,L=55;
int ch[N*L][26],cnt[N*L],id;
int ne[N*L];
queue <int> q;
char w[L],s[M];
int T,n;
void insert(char s[]){
int p=0;
for(int i=0;s[i];i++){
int x=s[i]-'a';
if(ch[p][x]==0)
ch[p][x]=++id;
p=ch[p][x];
}
cnt[p]++;
}
void bfs(){
for(int i=0;i<26;i++)
if(ch[0][i])
q.push(ch[0][i]);
while(!q.empty()){
int f=q.front();
for(int i=0;i<26;i++){
if(ch[f][i]){
int c=ch[f][i];
ne[c]=ch[ne[f]][i];
q.push(c);
}
else
ch[f][i]=ch[ne[f]][i];
}
q.pop();
}
}
int main(){
scanf("%d",&T);
while(T--){
memset(ch,0,sizeof(ch));
memset(cnt,0,sizeof(cnt));
memset(ne,0,sizeof(ne));
id=0;
scanf("%d",&n);
while(n--){
scanf("%s",w);
insert(w);
}
bfs();
scanf("%s",s);
int res=0;
for(int i=0,j=0;s[i];i++){
int x=s[i]-'a';
while(j&&ch[j][x]==0)
j=ne[j];
if(ch[j][x])
j=ch[j][x];
int p=j;
while(p!=0){
res+=cnt[p];
cnt[p]=0;
p=ne[p];
}
}
printf("%d\n",res);
}
return 0;
}
Cpp
INFO