评测记录

#include<bits/stdc++.h>
#define Code using
#define By namespace 
#define ZYY std;
Code By ZYY;
const int N = 2e6 + 10;
char s[N], t[N];
int n, tot = 0, din[N];
int mp[N], root = 0;
int ans[N];
struct Ac{
    int fail, ed, nxt[27];
    int flag = 0;
}tr[N];

inline void insert(char *s, int p) {
    int len = strlen(s + 1), now = root;
    for (int i = 1; i <= len; i++) {
        int u = s[i] - 'a';
        if (!tr[now].nxt[u]) tr[now].nxt[u] = ++tot;
        now = tr[now].nxt[u];
    }
    tr[now].ed = p;
    mp[p] = now; 
}

inline void Get_Fail() {
    queue<int> q;
    for (int i = 0; i < 26; i++) {
        int u = tr[root].nxt[i];
        if (!u) {tr[root].nxt[i] = root; continue;}
        tr[u].fail = root; 
        q.push(u);
        din[root]++;
    }

    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr[u].nxt[i];
            if (!v) {
                tr[u].nxt[i] = tr[tr[u].fail].nxt[i];
                continue;
            }
            tr[v].fail = tr[tr[u].fail].nxt[i];
            din[tr[v].fail]++;
            q.push(v);
        }
    }
}

inline void query(char *t) {
    int len = strlen(t + 1), now = root;
    for (int i = 1; i <= len; i++) {
        int u = t[i] - 'a';
        now = tr[now].nxt[u];
        tr[now].flag++;
    }
}

inline void topsort() {
    queue<int> q;
    for (int i = 1; i <= tot; i++) {
        if (!din[i]) q.push(i);
    }
    while (q.size()) {
        int u = q.front(); q.pop();
        if (tr[u].ed) ans[tr[u].ed] = tr[u].flag;
        int k = tr[u].fail;
        tr[k].flag += tr[u].flag;
        if (!--din[k]) q.push(k);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> (s + 1);
        insert(s, i);
    }
    cin >> (t + 1);
    Get_Fail();
    query(t);
    topsort();
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}