https://www.luogu.com.cn/problem/P3808
kmp + trie ：
1. 将 kmp 应用到树上，对 trie 树按层次遍历求出 next 数组
2. 由于第一层就是 0，因此不能把第一层加入队列中，而是将第二层加入队列。
注意：
1. 这里 next 数组需要初始化，因为遍历的下标不是按大小顺序来的。
2. 额外用个数组 v，标记单词是否已经出现过。因为出现过的单词，已经将次数清为 0，后面即使再出现，累加的也是 0。因此可以直接跳过累加。

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

using namespace std;

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

int n;
char s[M];
int nxt[N * 55];
int trie[N * 55][26], ed[N * 55], tot;
int q[N * 55];
int v[N * 55];

void insert(char s[]) {
    int p = 0;
    for(int i = 1; s[i]; i++) {
        int t = s[i] - 'a';
        if(trie[p][t] == 0) trie[p][t] = ++tot;
        p = trie[p][t];
    }
    ed[p]++;
}

void ACAM() {
    int hh = 0, tt = -1;
    for(int i = 0; i < 26; i++)
        if(trie[0][i]) q[++tt] = trie[0][i];

    while(hh <= tt) {
        int p = q[hh++];
        for(int t = 0; t < 26; t++) {
            int i = trie[p][t];
            if(!i) continue;

            int j = nxt[p];
            while(j && trie[j][t] == 0) j = nxt[j];
            if(trie[j][t]) j = trie[j][t];
            nxt[i] = j;
            q[++tt] = i;
        }
    }
}

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

    scanf("%s", s + 1);
    int ans = 0;
    for(int i = 1, j = 0; s[i]; i++) {
        int t = s[i] - 'a';
        while(j && trie[j][t] == 0) j = nxt[j];
        if(trie[j][t]) j = trie[j][t];
        int k = j;
        while(v[k] == 0 && k) {
            ans += ed[k];
            ed[k] = 0;
            v[k] = 1;
            k = nxt[k];
        }
    }

    printf("%d\n", ans);
    return 0;
}

优化：
trie 图