题意:就是求目标串中出现了几个模式串。
思路:用int型的end数组记录出现，AC自动机即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<queue>
#define maxn 500005
int T,n;
char s[];
struct Trie{
int root,L;
int next[maxn][],fail[maxn],end[maxn];
int newnode(){
for (int i=;i<;i++)
next[L][i]=-;
end[L++]=;
return L-;
}
void clear(){
L=;root=newnode();
}
void insert(char s[]){
int now=root,len=strlen(s);
for (int i=;i<len;i++){
if (next[now][s[i]-'a']==-) next[now][s[i]-'a']=newnode();
now=next[now][s[i]-'a'];
}
end[now]++;
}
void build(){
std::queue<int>Q;
int now=root;
for (int i=;i<;i++)
if (next[now][i]==-) next[now][i]=root;
else
fail[next[now][i]]=root,Q.push(next[now][i]);
while (!Q.empty()){
int now=Q.front();
Q.pop();
for (int i=;i<;i++){
if (next[now][i]==-)
next[now][i]=next[fail[now]][i];
else{
fail[next[now][i]]=next[fail[now]][i];
Q.push(next[now][i]);
}
}
}
}
int query(char s[]){
int now=root,len=strlen(s),res=;
for (int i=;i<len;i++){
now=next[now][s[i]-'a'];
int tmp=now;
while (tmp!=root){
res+=end[tmp];
end[tmp]=;
tmp=fail[tmp];
}
}
return res;
}
}ac;
int main(){
scanf("%d",&T);
while (T--){
scanf("%d",&n);
ac.clear();
for (int i=;i<n;i++){
scanf("%s",s);
ac.insert(s);
}
ac.build();
scanf("%s",s);
printf("%d\n",ac.query(s));
}
}