Trie+KMP+bfs

AC自动机=Trie+KMP ->可优化为Trie图
KMP      -> O(n) 求出某一个单词 出现在哪些地方 出现次数
AC自动机 -> O(n) 求出每一个单词 出现在哪些地方 出现次数
trie
       O
     s/ \h
     O   O
   h/ \a  \e
   O   O   O
 e/ \r  \y  \r
 O   O   O   O
类比 KMP 的 next[i] trie里的next数组代表最长的trie"相同前后缀"，如果不存在相同前缀则next[i]指向0
比如 she 中在trie树中最长存在相同前缀的后缀为he,其前缀和her的he 
此时 she 的 e 通过next指向 her的e

KMP中 由于while(j && p[i] != p[j+1]) j = next[j]; 
        直到 if(p[i]==p[j+1]) j++;
             next[i] = j;

        所以while这一行开始的时候的j是上一轮赋给next[i-1]时的j
        所以KMP:
        先求next[0] -> next[i-1]:前i-1组的信息 
        在前i-1组的信息上再去求next[i]
for(i=2;i<=m;i++)
{
    int j = next[i-1];
    while(j && p[i]!=p[j+1]) j = next[j];
    if(s[i]==p[j+1]) j++;
    next[i] = j;
}
类比KMP:
        自动机在trie中则是先求前i-1层的信息,再求第i层的信息
        那么逐层向下就可以用BFS来做
        while(hh<=tt)
        {
            t = q[hh++];取队列头节点 其值为自动机第i-1层某个结点的idx -> t对应的是next[i-1]中的i-1
            遍历头节点t所有的儿子
            26个字母
            for(i=0;i<26;i++)
            {
                p = tr[t][i];字母p为字母t的下一个字母,t对应的是next[i-1]中的i-1 那么p就对应i
                j = next[t]; j为前i轮循环后停在子串的下标 对比母串字母p[i] 和 子串j下标对应的字母的下一个字母p[j+1] 
                while(j && !tr[j][i]) j = next[j]; j的下一个字母(p[j+1])是不存在字母i(p[i])的 p[i]!=p[j+1]
                if(tr[j][i]) j=tr[j][i]; tr[j][i]代表idx为j的结点的儿子结点i的idx 
                next[p] = j; next[]中存的即为字母p为后缀最后一个所对应的trie中最长相同前缀的
            }
        }
类比符号:
            自动机       KMP
        t = q[hh++]; -> i-1
        p = tr[t][i] -> i    for i in (0,25)
        j = next[t]  -> j=next[i-1]  这里的j是指刚经过前i-1个点循环后第i次循环while还没开始的j
        在自动机里则表示刚经过前i-1层循环后第i层循环while还没开始的j
        所以其值等同于刚赋值给的next[i-1]，而自动机中t = i-1 所以j = next[i-1] = next[t]
tr[t][i]中代表字母的i-> p[i]         一个字母p[i]->trie可能有的26个字母
           !tr[j][i] -> p[i] != p[j+1]  tr[j][i] tr[j][i]表示j的下一个字母p[j+1]是不是这里的i(KMP中的p[i])

优化为trie图 
while(j && !tr[j][i]) j = next[j];
优化思路 在没有匹配时 把while循环多次跳 优化为 直接跳到ne指针最终跳到的位置
数学归纳法
假定在循环第i层时，前i-1层都求对了
那么ne[t]就是ne指针最终跳到的位置

C++ 代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N=10010,S=55,M=10000010;

int n;
int tr[N*S][26],cnt[N*S],idx;
char str[M];
int q[N*S],ne[N*S];
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];// 沿字符串字母idx继续往下走
    }
    cnt[p] ++;
}
void build()
{
    int hh=0,tt=-1;
    for(int i=0;i<26;i++)//根节点以及第一层结点都是指向根节点，所以直接从第一层开始搜，也就是根的所有儿子开始搜
    {
        if(tr[0][i])
            q[++tt] = tr[0][i];
    }

    while(hh<=tt)
    {
        int t = q[hh++];//队列popleft
        for(int i=0;i<26;i++)
        {
            int p = tr[t][i];//p:自动机中某个第i层结点的idx -> KMP中的i 
            // if(p)
            // {
            //     int j = ne[t];
            //     while(j && !tr[j][i]) j = ne[j];
            //     if(tr[j][i]) j = tr[j][i];
            //     ne[p] = j;
            //     q[++tt] = p;
            // }

            // 优化思路 在没有匹配时 把while循环多次跳 优化为 直接跳到ne指针最终跳到的位置
            // 数学归纳法
            // 假定在循环第i层时，前i-1层都求对了
            // 在第i层没找到字母i,那么去第i-1层父结点t的next指针的位置就是它最终应该跳到的位置
            if(!p) tr[t][i] = tr[ne[t]][i];//ne[t]:j  如果不存在儿子tr[t][i]的话
            // 如果存在儿子节点 则对儿子节点的next指针赋值为tr[ne[t]][i]
            else
            {
                ne[p] = tr[ne[t]][i];
                q[++tt] = p;
            }
        }
    }

}
int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            /*
            while(j && !tr[j][t]) j = ne[j];
            if(tr[j][t]) j=tr[j][t];
            int p = j;
             // she 和 he 的 e结点都有cnt[e]=1
                遍历到she的后缀he的时候 her的相同前缀he肯定是逐层遍历到了的 len(he)<len(she) 逐层遍历
                把所有ne 指针全部加一遍  比如当前p到了she的e  把cnt[p]+进res后 
                把p通过ne[p]跳到he的e 再加上此时指向he中e的p的cnt[p] 
            while(p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
            */
            j = tr[j][t];

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;//she he 把cnt[e]的用过了之后 res=2 此时再进来一个her 就不能再+he的cnt了,所以cnt[e]用过之后要置0
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}