莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. AC自动机 = Trie树 + KMP
2. tr 数组表示的是字典树
3. ne 数组表示以该字母为后缀的可以匹配成功的最长前缀的子节点
4. cnt 数组表示该单词出现的次数
5. 首先建立 Trie 树，可参考 Trie字符串统计
6. 其次是求解 ne 数组，用bfs的方式枚举每一层，并让当前点指向它的父节点所指向点的儿子节点
7. 最后是字符串匹配过程，每次取出当前字母，保证当前字母前所存在的单词出现次数都已统计

Trie可参考： Trie字符串统计
KMP可参考： KMP字符串

#include<bits/stdc++.h>

using namespace std;

const int N = 500010, M = 1000010;

int n;
int tr[N][26],cnt[N],idx;
int ne[N];
char str[M];

//建立 Trie 树
void insert()
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
    }
    cnt[p]++;
}

//求 ne 数组
void build()
{
    //将第一层的所有点加入队列
    queue<int> q;
    for(int i=0;i<26;i++)
        if(tr[0][i])
            q.push(tr[0][i]);

    while(q.size())
    {
        //取出队头
        int t=q.front();
        q.pop();

        //枚举下一层
        for(int i=0;i<26;i++)
        {
            int p=tr[t][i];
            if(!p) tr[t][i]=tr[ne[t]][i];
            else 
            {
                //让当前点指向它的父节点所指向点的儿子节点
                ne[p]=tr[ne[t]][i];
                q.push(p);
            }
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(tr,0,sizeof tr);
        memset(cnt,0,sizeof cnt);
        memset(ne,0,sizeof ne);
        idx=0;

        cin>>n;
        for(int i=0;i<n;i++) 
        {
            cin>>str;
            insert();
        }

        build();

        cin>>str;

        //字符串匹配，每次取出当前字母，保证当前字母前所存在的单词出现次数都已加入res
        int res=0;
        for(int i=0,j=0;str[i];i++)
        {
            j=tr[j][str[i]-'a'];
            int p=j;
            while(p)
            {
                res+=cnt[p];
                cnt[p]=0;
                p=ne[p];
            }
        }

        cout<<res<<endl;
    }

    return 0;
}