https://www.luogu.com.cn/problem/P5357
需要用拓扑序来优化。
1. 在 trie 树中，其实就是从低往上累加的过程。
2. 队列中存的顺序就是一个拓扑序，逆序累加即可。

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 2e5 + 10, S = 2e6 + 10;

int n;
char s[S];
int trie[N][26], nxt[N], f[N], q[N], tot;
int pot[N];

void insert(int x) {
    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];
    }
    pot[x] = p;
}

void ACAM() {
    int hh = 0, tt = -1;
    for(int t = 0; t < 26; t++)
        if(trie[0][t]) q[++tt] = trie[0][t];
    while(hh <= tt) {
        int p = q[hh++];
        for(int t = 0; t < 26; t++) {
            int i = trie[p][t];
            if(i == 0) 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() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        insert(i);
    }
    ACAM();

    scanf("%s", s + 1);
    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];
        f[j]++;
    }
    for(int i = tot - 1; i >= 0; i--)
        f[nxt[q[i]]] += f[q[i]];
    for(int i = 1; i <= n; i++)
        printf("%d\n", f[pot[i]]);
    return 0;
}