AC自动机
本质上是 KMP+Trie。
每个节点存储的 \(ne\) 类似于 KMP，表示最长公共前后缀（前缀可以是从根出发的任意一条路径）。代码可以从 KMP 一一对应过来。
有 Trie 图优化，本质上可以直接背代码。
#include<cstdio>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=10010,S=55;
int T,n,tr[N*S][26],idx,cnt[N*S],q[N*S],ne[N*S];
char s[N*100];
void insert(char s[]){
int p=0;
for(int i=0;s[i];++i){
int &now=tr[p][s[i]-'a'];
if(!now)now=++idx;
p=now;
}
++cnt[p];
}
void AC(){
int hh=0,tt=0;
L(i, 26)if(tr[0][i])q[tt++]=tr[0][i];
while(hh!=tt){
int t=q[hh++];
L(i, 26){
int p=tr[t][i];
if(!p)tr[t][i]=tr[ne[t]][i];
else ne[p]=tr[ne[t]][i],q[tt++]=p;
}
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&T);
W(T){
int res=0;
memset(ne,0,sizeof ne);
memset(cnt,0,sizeof cnt);
memset(tr,0,sizeof tr);
idx=0;
scanf("%d",&n);
E(i, n){
scanf("%s",s);
insert(s);
}
AC();
scanf("%s",s);
for(int i=0,j=0;s[i];++i){
int c=s[i]-'a';
j=tr[j][c];
int tmp=j;
while(tmp&&~cnt[tmp]){
res+=cnt[tmp];
cnt[tmp]=-1;
tmp=ne[tmp];
}
}
printf("%d\n",res);
}
return 0;
}