AC自动机（优化版）

#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;
}