python/TangDou/AcWing/AcAutomation/P5357_DiTui.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
const int M = 2000010; //文本串长度

int f[N];
char s[N];
char T[M];
int tr[N][26], idx, ne[N], id[N];

void insert(char *s, int x) {
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int t = s[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++idx;
        p = tr[p][t];
    }
    id[x] = p;
}

//构建AC自动机
int q[N], hh, tt = -1;
void bfs() {
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) q[++tt] = tr[0][i];

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0; i < 26; ++i) {
            if (tr[t][i]) {
                ne[tr[t][i]] = tr[ne[t]][i];
                q[++tt] = tr[t][i];
            } else
                tr[t][i] = tr[ne[t]][i];
        }
    }
}

void query(char *s) {
    int p = 0;
    for (int i = 0; s[i]; i++) { // 枚举文本串每一个字符
        int t = s[i] - 'a';      // 字符映射的数字t,可以理解为边
        p = tr[p][t];            // 走进去，到达的位置替换p
        f[p]++;                  // 标识此位置有人走过，记录走的次数
    }
}

int main() {
    //加快读入
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(s, i);
    }
    //构建AC自动机
    bfs();
    //文本串
    cin >> T;
    query(T);
    for (int i = idx; i; i--) f[ne[q[i]]] += f[q[i]]; //一路向上，计算叠加值
    //输出
    for (int i = 1; i <= n; i++) printf("%d\n", f[id[i]]);
    return 0;
}