AC自动机

const int N = 1e5 + 5;

struct AC {
    vector<vector<int>> nex;
    vector<int> flag[N];
    vector<int> fail;
    map<string, int> id;
    vector<int> cnt;
    vector<string> inv;
    int idx = 0;
    AC() {
        nex.resize(N, vector<int>(26));
        fail.resize(N);
        cnt.resize(N);
        inv.resize(N);
    }
    void init() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < 26; j++) {
                nex[i][j] = 0;
            }
            fail[i] = 0;
        }
        for (int i = 0; i < N; i++) {
            flag[i].clear();
            cnt[i] = 0;
        }

        id.clear();
        inv.clear();
        idx = 0;
    }
    void add(const string &s, int I) {
        id[s] = I;
        inv[I] = s;
        int p = 0;
        for (int i = 0; i < s.size(); i++) {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++idx;
            p = nex[p][c];
        }
        flag[p].push_back(id[s]);
    }
    void get_fail() {
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (nex[0][i]) q.push(nex[0][i]);
        }
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            for (int i = 0; i < 26; i++) {
                if (nex[x][i]) {
                    fail[nex[x][i]] = nex[fail[x]][i];
                    q.push(nex[x][i]);
                } else {
                    nex[x][i] = nex[fail[x]][i];
                }
            }
        }
    }
    void solve(const string &s) {
        get_fail();
        int p = 0;
        for (int i = 0; i < s.size(); i++) {
            p = nex[p][s[i] - 'a'];
            for (int j = p; j; j = fail[j]) {

                for (auto t : flag[j]) {
                    cnt[t]++;
                }
            }
        }
    }
} ac;
// 每次新的 test 进入时要调用 init 函数
// 对于每个模式串，调用 ac.add(t, idx)
// 然后对于文本串调用 ac.solve(s)
// 最终 cnt[idx] 代表的是对应的模式串出现的次数