洛谷P3808 【模板】AC 自动机（简单版）题解 AC自动机模板题

题目链接：https://www.luogu.com.cn/problem/P3808

AC自动机模板题。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;

struct Node {
    int son[26], fail, id;
    Node() {}
    Node(int _id) {
        memset(son, 0, sizeof(son));
        fail = 0;
        id = _id;
    }
} tr[maxn];
int n, cnt, cc[maxn];
char s[maxn];

void ins(char *s, int id) {
    int u = 0;
    for (; *s; s++) {
        int c = (*s) - 'a';
        if (!tr[u].son[c])
            tr[ tr[u].son[c] = ++cnt ] = Node(0);
        u = tr[u].son[c];
    }
    tr[u].id = id;
    cc[u]++;
}

void build() {
    queue<int> que;
    for (int i = 0; i < 26; i++)
        if (tr[0].son[i])
            que.push(tr[0].son[i]);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (int i = 0; i < 26; i++) {
            int v = tr[u].son[i];
            if (!v) continue;
            int x = tr[u].fail;
            while (x && !tr[x].son[i])
                x = tr[x].fail;
            tr[v].fail = tr[x].son[i];
            que.push(v);
        }
    }
}

bool vis[maxn];
int cal(char *s) {
    int u = 0, cnt = 0;
    for (; *s; s++) {
        int c = (*s) - 'a';
        while (u && !tr[u].son[c])
            u = tr[u].fail;
        if (tr[u].son[c])
            u = tr[u].son[c];
        if (tr[u].id && !vis[tr[u].id]) {
            vis[tr[u].id] = true;
            cnt += cc[u];
        }
    }
    return cnt;
}

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