C++ – AC 自动机

struct node_t {
    int nxt[26];
    int fail;
    int num;
};

int cnt;
node_t trie[maxn];

void trie_insert(char s[]) {
    int u = 0;
    int len = strlen(s);
    for (int i = 0; i < len; ++i) {
        if (!trie[u].nxt[s[i] - 'a'])
            trie[u].nxt[s[i] - 'a'] = ++cnt;
        u = trie[u].nxt[s[i] - 'a'];
    }
    trie[u].num++;
}

void trie_fail() {
    queue<int> q;
    for (int i = 0; i < 26; ++i) {
        if (trie[0].nxt[i]) {
            trie[trie[0].nxt[i]].fail = 0;
            q.push(trie[0].nxt[i]);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < 26; ++i) {
            int v = trie[u].nxt[i];
            if (v) {
                trie[v].fail = trie[trie[u].fail].nxt[i];
                q.push(v);
            } else trie[u].nxt[i] = trie[trie[u].fail].nxt[i];
        }
    }
}

int trie_ask(char s[]) {
    int len = strlen(s);
    int ans = 0;
    int u = 0;
    for (int i = 0; i < len; ++i) {
        u = trie[u].nxt[s[i] - 'a'];
        int v = u;
        while (v && ~trie[v].num) {
            ans += trie[v].num;
            trie[v].num = -1;
            v = trie[v].fail;
        }
    }
    return ans;
}