AC自动机

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define int long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int N=1e4;
const int M=1e6;
const int L=50;
int ch[N*L+50][26],id,cnt[N*L+50];
int ne[N*L+50];
int T,n;
int q[N*L+50];
string w,s;
void insert(string w)
{
	int p=0;
	for(int i=0;i<w.size();i++)
	{
		int x=w[i]-'a';
		if(ch[p][x]==0)
		{
			ch[p][x]=++id;
		}
		p=ch[p][x];
	}
	cnt[p]++;
}
void bfs()
{
	int h=1,t=0;
	for(int i=0;i<26;i++)
	{
		if(ch[0][i])
		{
			q[++t]=ch[0][i];
		}
	}
	while(h<=t)
	{
		int f=q[h];
		for(int i=0;i<26;i++)
		{
			if(ch[f][i])
			{
				int c=ch[f][i];
				int j=ne[f];
				while(j&&ch[j][i]==0)
				{
					j=ne[j];
				}
				if(ch[j][i])
				{
					j=ch[j][i];
				}
				ne[c]=j;
				q[++t]=c;
			}
		}
		h++;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)
	{
		memset(ch,0,sizeof(ch));
		memset(cnt,0,sizeof(cnt));
		memset(ne,0,sizeof(ne));
		id=0;
		cin>>n;
		while(n--)
		{
			cin>>w;
			insert(w);
		}
		bfs();
		cin>>s;
		int res=0;
		for(int i=0,j=0;s[i]!='\0';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];
			}
		}
		cout<<res<<endl;
	}
	return 0;
}