AC自动机

即在trie上kmp。AC自动机是一种多模式串匹配算法，用于在一个文本串中查找多个模式串。

注意到，AC自动机的\(fail\)也构成了一个树形结构。我们只需要在操作完进行一个离线拓扑排序就不用每次匹配到一个点，暴力跑完所有fail确认是哪些模式串。

struct AC {
    vector<int>end[MAXN];
    int tr[MAXN][26];
    int fail[MAXN], tot, in[MAXN];
    int cnt[MAXN], tag[MAXN];
    void insert(char* s, int n, int id) {
        int p = 0;
        for (int i = 1; i <= n; ++i) {
            if (tr[p][s[i] - 'a'] == 0)tr[p][s[i] - 'a'] = ++tot;
            p = tr[p][s[i] - 'a'];
        }
        end[p].push_back(id);
    }

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

    void work(char* s, int n) {
        int p = 0;
        for (int i = 1; i <= n; ++i) {
            p = tr[p][s[i] - 'a'];
            tag[p]++;
        }
    }

    void topsort() {
        queue<int>q;
        for (int i = 1; i <= tot; ++i)
            if (!in[i])q.push(i);
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (auto x : end[t])
                cnt[x] = tag[t];
            in[fail[t]]--;
            tag[fail[t]] += tag[t];
            if (!in[fail[t]])q.push(fail[t]);
        }
    }

    void clear(int n) {
        for (int i = 0; i <= tot; ++i) {
            end[i].clear(), fail[i] = in[i] = tag[i] = 0;
            memset(tr[i], 0, sizeof(tr[i]));
        }
        for (int i = 1; i <= n; ++i)cnt[i] = 0;
        tot = 0;
    }

}ac;

例题：
luogu: P5357 【模板】AC 自动机
luogu: P2292 [HNOI2004] L 语言
HDU:7455 在 A 里面找有 C 的 B