AC自动机板子题：
trie bfs kmp
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
const int M=1e6 10,N=1e4 10,S=55;
int t,n,tr[N*S][26],cnt[N*S],idx,ne[N*S];
char s[M];
void insert(){
int p=0;
for(int i=0;s[i];i ){
int t=s[i]-'a';
if(!tr[p][t])tr[p][t]= idx;
p=tr[p][t];
}
cnt[p] ;
}
void build(){
queue<int>q;
for(int i=0;i<26;i ){
if(tr[0][i])q.push(tr[0][i]);
}
while(q.size()){
int t=q.front();
q.pop();
for(int i=0;i<26;i ){
int p=tr[t][i];
if(!p)tr[t][i]=tr[ne[t]][i];
else{
ne[p]=tr[ne[t]][i];
q.push(p);
}
}
}
}
int main(){
cin>>t;
while(t--){
memset(cnt,0,sizeof cnt);
memset(tr,0,sizeof tr);
memset(ne,0,sizeof ne);
scanf("%d",&n);
for(int i=1;i<=n;i ){
scanf("%s",s);
insert();
}
scanf("%s",s);
build();
int res=0;
for(int i=0,j=0;s[i];i ){
int t=s[i]-'a';
j=tr[j][t];
int p=j;
while(p){
res =cnt[p];
cnt[p]=0;
p=ne[p];
}
}printf("%dn",res);
}
}
