【算法】AC自动机
【题解】本题注意题意是多少关键字能匹配而不是能匹配多少次，以及可能有重复单词。
询问时AC自动机与KMP最大的区别是因为建立了trie，所以对于目标串T与自动机串是否匹配只需要直接访问对应结点，而不用真的比较。
因此可以预处理出拥有对应节点的失配串，不用一次一次跑前跑去找一样的。
然后还有就是一个结点可能对应多个串，所以需要last使统计答案完整。
AC自动机的细节标注在代码里了。
AC自动机过程：
[trie]
for 长度
if(!ch[u][c])初始化,ch[u][c]=++sz;
else u=ch[u][c];
val[u]=...;
[getfail]
初始进队
队：u
for 26(处理u点后续节点)
if(!u)ch[x][c]=ch[p[x][c],continue;（没有该点，则考虑直接走失配直到有此点的串，由于层层前推实际上前一个即可）
u进队;（有此点）
int j=p[x];
while(j>0&&!ch[j][c])j=p[j];（走失配直到有此点的串）
p[u]=ch[j][c];（记录失配边）
last[u]=val[p[u]]?p[u]:last[p[u]];（记录同结尾价值点）
[find]
[askans]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxnode=,maxn=,maxlen=;
int val[maxnode],sz,ch[maxnode][],p[maxnode],last[maxnode],q[];
long long ans;
char s[maxlen];
int idx(char c){return c-'a'+;}
void trie(char s[])
{
int u=,m=strlen(s+);
for(int i=;i<=m;i++)
{
int c=idx(s[i]);
if(!ch[u][c])
{
sz++;
memset(ch[sz],,sizeof(ch[sz]));//初始化
val[sz]=;//初始化
ch[u][c]=sz;
}
u=ch[u][c];
}
val[u]++;
}
void getfail()
{
int head=,tail=;//初始队列不能有队头！
p[]=;last[]=;//trie根初始化
for(int c=;c<=;c++)
{
int u=ch[][c];
if(u){p[u]=;last[u]=;q[tail++]=u;}
}
while(head!=tail)
{
int x=q[head++];if(head>)head=;
for(int c=;c<=;c++)
{
int u=ch[x][c];
if(!u){ch[x][c]=ch[p[x]][c];continue;}//直接得到可匹配字符串，无则为0。
q[tail++]=u;if(tail>)tail=;
int j=p[x];
while(j>&&!ch[j][c])j=p[j];
p[u]=ch[j][c];
last[u]=val[p[u]]?p[u]:last[p[u]];
}
}
}
void askans(int j)
{
while(j)
{
ans+=val[j];
val[j]=;
j=last[j];
}
}
void find(char s[])
{
int m=strlen(s+);
int j=;
for(int i=;i<=m;i++)
{
int c=idx(s[i]);
j=ch[j][c];//直接得到
if(val[j])askans(j);
else if(last[j])askans(last[j]);
}
}
int main()
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int n;
scanf("%d",&n);
sz=;//根节点标号为0
memset(ch[],,sizeof(ch[]));//初始化根节点即可，建树中需要会继续清理，保持有效与无效结点中间始终存在断层。
for(int i=;i<=n;i++)
{
scanf("%s",s+);
trie(s);//传过去的一定要是s，不能是s+1
}
getfail();
scanf("%s",s+);
ans=;
find(s);
printf("%lld\n",ans);
}
return ;
}