【字符串】AC自动机

struct ACM {

    static const int MAXN = 1e6 + 10;

    int ch[MAXN][26], fail[MAXN];
    int cnt;

    int R[MAXN];

    void Init() {
        ms(ch[0]), fail[0] = 0;
        cnt = 0;
    }

    int NewNode() {
        int o = ++cnt;
        ms(ch[o]);
        fail[o] = 0;
        R[o] = 0;
        return o;
    }

    void Insert(char *s) {
        int u = 0;
        for (int i = 1; s[i]; ++i) {
            if (!ch[u][s[i] - 'a'])
                ch[u][s[i] - 'a'] = NewNode();
            u = ch[u][s[i] - 'a'];
        }
        ++R[u];
    }

    void Build() {
        static queue<int> Q;
        while(!Q.empty())
            Q.pop();
        for(int i = 0; i < 26; ++i) {
            if(ch[0][i])
                Q.push(ch[0][i]);
        }
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for(int i = 0; i < 26; ++i) {
                if(ch[u][i]) {
                    fail[ch[u][i]] = ch[fail[u]][i];
                    Q.push(ch[u][i]);
                } else {
                    ch[u][i] = ch[fail[u]][i];
                }
            }
        }
    }

    int Query(char *t) {
        int u = 0, res = 0;
        for (int i = 1; t[i]; ++i) {
            u = ch[u][t[i] - 'a'];
            for (int j = u; j && R[j] != -1; j = fail[j])
                res += R[j], R[j] = -1;
        }
        return res;
    }

} acm;

AC自动机 二次加强版

struct ACM {

    static const int MAXN = 2e6 + 10;

    int ch[MAXN][26], fail[MAXN];
    int cnt;

    vector<int> R[MAXN];
    vector<int> G[MAXN];

    void Init() {
        ms(ch[0]), fail[0] = 0;
        cnt = 0;
    }

    int NewNode() {
        int o = ++cnt;
        ms(ch[o]);
        fail[o] = 0;
        R[o].clear();
        return o;
    }

    void Insert(char *s, int id) {
        int u = 0;
        for (int i = 1; s[i]; ++i) {
            if (!ch[u][s[i] - 'a'])
                ch[u][s[i] - 'a'] = NewNode();
            u = ch[u][s[i] - 'a'];
        }
        R[u].eb(id);
    }

    void Build() {
        static queue<int> Q;
        while(!Q.empty())
            Q.pop();
        for(int i = 0; i < 26; ++i) {
            if(ch[0][i])
                Q.push(ch[0][i]);
        }
        while(!Q.empty()) {
            int u = Q.front();
            Q.pop();
            for(int i = 0; i < 26; ++i) {
                if(ch[u][i]) {
                    fail[ch[u][i]] = ch[fail[u]][i];
                    Q.push(ch[u][i]);
                } else {
                    ch[u][i] = ch[fail[u]][i];
                }
            }
        }
        for(int i = 0; i <= cnt; ++i)
            G[i].clear();
        for(int i = 1; i <= cnt; ++i)
            G[fail[i]].eb(i);
    }

    int vis[MAXN], ans[MAXN];
    void dfs(int u) {
        for(int &v : G[u]) {
            dfs(v);
            vis[u] += vis[v];
        }
        for(auto &i : R[u])
            ans[i] = vis[u];
    }

    void Query(char *t) {
        for(int i = 0; i <= cnt; ++i)
            vis[i] = 0;
        int u = 0;
        for(int i = 1; t[i]; ++i) {
            u = ch[u][t[i] - 'a'];
            ++vis[u];
        }
        dfs(0);
    }

} acm;