AC自动机 | Moonglade

P3808 【模板】AC自动机（简单版）

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

struct Aho_Corasick_Automaton {
    int c[N][26], f[N], v[N], cnt;
    void ins(char *p) {
        int now = 0, len = strlen(p);
        for (int i = 0; i < len; i++) {
            if (c[now][p[i] - 'a']) now = c[now][p[i] - 'a'];
            else now = c[now][p[i] - 'a'] = ++cnt;
        }
        v[now]++;
    }
    void build() {
        queue<int> q;
        for (int i = 0; i < 26; i++) {
            if (c[0][i]) {
                q.push(c[0][i]);
                f[c[0][i]] = 0;
            }
        }
        while(!q.empty()) {
            int now = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                if (c[now][i]) {
                    q.push(c[now][i]);
                    f[c[now][i]] = c[f[now]][i];
                } else c[now][i] = c[f[now]][i];
            }
        }
    }
    int query(char *s) {
        int len = strlen(s), res = 0, now = 0;
        for (int i = 0; i < len; i++) {
            now = c[now][s[i] - 'a'];
            for (int t = now; t && v[t] != -1; t = f[t]) {
                res += v[t];
                v[t] = -1;
            }
        }
        return res;
    }
}AC;

int n;

char s[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        AC.ins(s);
    }
    AC.build();
    scanf("%s", s);
    printf("%d\n", AC.query(s));
    return 0;
}