AC自动机

#AC自动机 时间复杂度： AC自动机是多模匹配算法，能在一个文本串中同时查找多个不同的模式串。 注： “fail指针” 、 “蓝色虚点”

#include<bits/stdc++.h>

using namespace std;

const int maxn = 4e5+1; // 匹配串的总长度

int tree[maxn][26], tot, fail[maxn];
int id[maxn], dep[maxn], en[maxn], sz[maxn][2];


void build(int x, string t) {
    int pos = 0, m = t.size();
    for(int i = 0; i < m; ++ i) {
        if (!tree[pos][t[i]-'a']) tree[pos][t[i]-'a'] = ++tot;
        pos = tree[pos][t[i]-'a'];
        dep[pos] = i+1;
    }
    id[x] = pos;
}


void gfail() {
    queue<int> que;
    for(int i = 0; i < 26; ++ i) {
        if (tree[0][i]) {
            fail[tree[0][i]] = 0;
            que.push(tree[0][i]);
        }
    }
    while(!que.empty()) {
        int x = que.front();
        que.pop();
        for(int i = 0; i < 26; ++ i) {
            if (tree[x][i] == 0) tree[x][i] = tree[fail[x]][i];
            else {
                fail[tree[x][i]] = tree[fail[x]][i];
                que.push(tree[x][i]);
            }
        }
    }
}

void query(string s) {
    int pos = 0, n = s.size();
    for(int i = 0; i < n; ++ i) {
        pos = tree[pos][s[i]-'a'];
        int k = pos;
        while(k) {
            sz[k][0] ++;
            if (en[k] + dep[k] <= i+1) {
                sz[k][1] ++;
                en[k] = i+1;
            }
            k = fail[k];
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin >> s;
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++ i) {
        string t;
        cin >> t;
        build(i, t);
    }
    gfail();
    query(s);
    for(int i = 1; i <= n; ++ i) {
        cout << sz[id[i]][0] << " \n"[i==n];
    }
    for(int i = 1; i <= n; ++ i) {
        cout << sz[id[i]][1] << " \n"[i==n];
    }

    for(int i = 0; i <= tot; ++ i) {
        en[i] = sz[i][0] = sz[i][1] = 0;
        for(int j = 0; j < 26; ++ j) tree[i][j] = 0;
    }
    tot = 0;
    return 0;
}