详细解释可以参考代码注释

参考了各路大神，写成了与AC自动机原版算法更适配的版本
希望和大家一起学习

时间复杂度 $O(n)$

参考内容

1. y总Trie树讲解
2. b站UESTCACM 每周算法讲堂 AC自动机

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int N = 10010, M = 1e6+10;

int T, n;

char S[M];
queue<int> q;

//定义我们的AC自动机
struct Aho{
    struct acState{
        int son[26];
        int fail;
        int cnt; //到这一状态有多少个串，与yz代码里的cnt含义一致
    }states[N * 50];

    //size记录自动机共有多少个节点（与yz代码里的idx含义一致）
    int size;

    void init(){
        for(int i = 0; i < N * 50; i++){
            memset(states[i].son, 0, sizeof(states[i].son));
            states[i].fail = states[i].cnt = 0;
        }
        //至少有一个空节点
        size = 1;
    }



    //yz的经典构建Trie树方法
    void insert(char *str){
        int p = 0;
        for(int i = 0; str[i]; i++){
            int t = str[i] - 'a';
            if(!states[p].son[t]) states[p].son[t] = size++;
            p = states[p].son[t];
        }
        states[p].cnt++;
    }



    //构造fail指针
    void build(){
        //因为算法中fafail的存在，逻辑上应当先处理好父亲再处理孩子——从上往下遍历。利用宽搜来实现（队列数据结构）

        //将0节点的fail指针指向-1
        states[0].fail = -1;

        q.push(0);
        while(!q.empty()){
            int u = q.front();
            q.pop();

            for(int i = 0; i < 26; i++){
                if(states[u].son[i]){

                    //如果u是0节点，则根据性质：第一层的节点的fail指针都指向root（0节点）
                    if(u == 0) states[states[u].son[i]].fail = 0;
                    else{
                        //v即为fafail，记录父节点fail指针指向的节点
                        int v = states[u].fail;
                        while(v != -1){
                            if(states[v].son[i]){
                                //如果fafail指向的节点有与当前节点相同的字母，则将当前指针指向该节点
                                states[states[u].son[i]].fail = states[v].son[i];
                                break;
                            }
                            v = states[v].fail;
                        }
                        //遍历到最后也没有找到，则当前节点fail指向0节点（root）
                        if(v == -1) states[states[u].son[i]].fail = 0;
                    }
                    q.push(states[u].son[i]);
                }
            }
        }
    }



    //计算以当前节点为后缀的单词有多少个——当前节点now所有fafail cnt的和
    int get_cnt(int now){
        int res = 0;
        while(now){
            res += states[now].cnt;
            //为了不重复计算将匹配过的置为零
            states[now].cnt = 0;
            now = states[now].fail;
        }
        return res;
    }



    //匹配str串中有几个单词
    int match(char *str){
        //result记录匹配到单词的个数
        int res = 0;

        int p = 0;
        for(int i = 0; str[i]; i++){
            int t = str[i] - 'a';
           if(states[p].son[t]) p = states[p].son[t];
           //没找到跳到fafail指向的节点
           else{
               int fafail = states[p].fail;
               //找不到和当前节点相同字母或没有走到root时一直找fail
               while(fafail != -1 && states[fafail].son[t] == 0) fafail = states[fafail].fail;
               //一直没找到，最后返回0节点
               if(fafail == -1) p = 0;
               //否则去往符合的节点
               else p = states[fafail].son[t];
           }
           //判断以当前节点字母结尾的找到了几个匹配的单词
           if(states[p].cnt != -1) res += get_cnt(p);
        }
        return res;
    }


}aho;



int main(){
    scanf("%d", &T);
    while(T--){
        aho.init();
        scanf("%d", &n);
        for(int i = 0; i < n; i++){
            scanf("%s", S);
            aho.insert(S);
        }
        aho.build();
        scanf("%s", S);
        printf("%d\n", aho.match(S));
    }
    return 0;
}