模板：
#include<bits/stdc++.h> using namespace std; const int N=500005; struct ac_automation { int trie[N][26]; int e[N]; //字符串的结尾标记 int fail[N]; int L,root; int newnode() //清空该节点下面所有子节点并得到一个新节点 { for(int i=0;i<26;i++) trie[L][i]=-1; e[L++]=0; return L-1; } void init() { L=0; root=newnode(); } void insert(char *s) //结尾节点e数组为1非结尾节点e数组为0 { int p=root; for(int i=0;s[i];i++) { int k=s[i]-'a'; if(trie[p][k]==-1)trie[p][k]=newnode(); p=trie[p][k]; } e[p]++; } void build()// 一个节点的fail节点为,该节点的父节点的fail节点与该节点出边相同的节点 { queue<int>q; fail[root]=root; for(int i=0;i<26;i++) { if(trie[root][i]==-1) trie[root][i]=root; else { fail[trie[root][i]]=root; q.push(trie[root][i]); } } while(!q.empty()) { int k=q.front(); q.pop(); for(int i=0;i<26;i++) { if(trie[k][i]==-1) { trie[k][i]=trie[fail[k]][i]; } else { fail[trie[k][i]]=trie[fail[k]][i]; q.push(trie[k][i]); } } } } int query(char *t) { int p=root, res=0; for(int i=0;t[i];i++) { p=trie[p][t[i]-'a']; for(int j=p; j&&~e[j]; j=fail[j])res+=e[j],e[j]=-1; } return res; } }ac; int n; int t; char s[1000010]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); ac.init(); for(int i=1;i<=n;i++) { scanf("%s",s); ac.insert(s); } ac.build(); scanf("%s",s); printf("%d\n",ac.query(s)); } return 0; }
)
