1. 题目

传送门=￣ω￣=

2. 题解

AC 自动机模板题
其实 AC 自动机就是在 trie 树上跑 kmp。。。
一开始为了追求代码短写递归，结果不知道怎么的不停地WA。。。
调一晚上放弃了，老老实实地打了 bfs 版的。。。
于是很快就AC了

真是气人！

推荐一篇 AC 自动机的博客：
http://blog.csdn.net/niushuai666/article/details/7002823

还有一个 AC 自动机的讲解视屏（bilibili 上的）：
https://www.bilibili.com/video/av6295004/

哦对了，还有我的代码：

#include <bits/stdc++.h>
#define cls(a) (memset((a),0,sizeof(a)))
using namespace std;
int t,n,nxt[500005][26],e[500005],fail[500005],cnt,ans;
char s[1000005];
queue<int> que;
void insert()
{
    int l=strlen(s),p=1;
    for(int i=0,tem;i<l;i++)
    {
        tem=s[i]-'a';
        if(!nxt[p][tem])nxt[p][tem]=++cnt;
        p=nxt[p][tem];
    }
    e[p]++;
}
void init()
{
    que.push(1);
    while(!que.empty())
    {
        for(int i=0,j;i<26;i++)
            if(nxt[que.front()][i])
            {
                j=fail[que.front()];
                while(!nxt[j][i])j=fail[j];
                fail[nxt[que.front()][i]]=nxt[j][i],que.push(nxt[que.front()][i]);
            }
        que.pop();
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n),cls(nxt),cls(e),cls(fail),cnt=1,ans=0;
        for(int i=1;i<=n;i++)scanf("%s",s),insert();
        for(int i=0;i<26;i++)nxt[0][i]=1;
        init(),scanf("%s",s);
        for(int i=0,j=1,l=strlen(s);i<l;i++)
        {
            while(!nxt[j][s[i]-'a'])j=fail[j];
            j=nxt[j][s[i]-'a'];
            for(int k=j;k&&e[k]!=-1;k=fail[k])ans+=e[k],e[k]=-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}