一、适用场景

多模式串匹配问题：给定一堆模式串，一个长文本，一次性找出文本里所有出现过的模式串。 暴力：每个模式串单独 KMP，总复杂度爆炸。 AC 自动机 = Trie 字典树 + KMP 失配指针 (fail) + 后缀链优化，线性处理。

二、三大组成部分

1. Trie 树（字典树）

把所有模式串插入一棵多叉树：

• 节点：代表字符；
• 末尾节点标记：该位置存在一个完整模式串； 作用：存储所有模式串公共前缀，减少重复存储。

2. fail 失配指针（对应 KMP 的 next）

每个节点设 fail 指针： 当前节点匹配失败时，跳到最长真后缀对应的节点，和 KMP next 思想完全同源。 用 BFS 层序遍历构建 fail。

3. 后缀链优化（last/end 链）

一个节点的 fail 链上所有节点，都是当前后缀能匹配到的模式串。 每次查询顺着 fail 链遍历会重复遍历，预处理cnt/end优化，避免重复走链。

三、完整原理流程

1. 建 Trie：把所有模式串插入树，记录串尾标记；
2. BFS 构建 fail 指针：根节点 fail=0，根的直接子节点 fail=0；逐层求每个点的 fail；
3. 文本查询：顺着 Trie 走，失配跳 fail，统计所有匹配到的模式串。

四、标准模板（C++，竞赛常用，小写字母）

基础版（统计每个串出现次数）

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1e6 + 10;
int trie[MAXN][26];  // trie[u][c]：u节点走字符c到的子节点
int fail[MAXN];       // 失配指针
int endpos[MAXN];    // endpos[u]：以u结尾的模式串数量
int tot;             // 节点编号

// 初始化
void init() {
    memset(trie, 0, sizeof trie);
    memset(fail, 0, sizeof fail);
    memset(endpos, 0, sizeof endpos);
    tot = 0;
}

// 插入模式串s
void insert(const string &s) {
    int u = 0;
    for (char ch : s) {
        int c = ch - 'a';
        if (!trie[u][c]) trie[u][c] = ++tot;
        u = trie[u][c];
    }
    endpos[u]++; // 多个相同串则计数+1
}

// BFS构建fail指针
void build() {
    queue<int> q;
    for (int c = 0; c < 26; c++) {
        if (trie[0][c]) {
            fail[trie[0][c]] = 0;
            q.push(trie[0][c]);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int c = 0; c < 26; c++) {
            int v = trie[u][c];
            if (v) {
                // 找v的fail
                int f = fail[u];
                while (f && !trie[f][c]) f = fail[f];
                fail[v] = trie[f][c];
                q.push(v);
            }
        }
    }
}

// 查询文本s，返回所有匹配总数
int query(const string &s) {
    int u = 0, res = 0;
    for (char ch : s) {
        int c = ch - 'a';
        // 失配跳fail
        while (u && !trie[u][c]) u = fail[u];
        u = trie[u][c];
        // 遍历fail链累加答案
        int p = u;
        while (p) {
            res += endpos[p];
            p = fail[p];
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    init();
    int n; cin >> n;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        insert(s);
    }
    build();
    cin >> s;
    cout << query(s) << endl;
    return 0;
}

五、优化版（拓扑预处理，消除查询时 while 链，大数据必用）

上面query里while(p)顺着 fail 链累加会被卡常，预处理拓扑序累加 endpos，查询时直接取：

// 新增拓扑优化
int in[MAXN]; // 入度
void build_opt() {
    queue<int> q;
    vector<int> topo;
    for (int c = 0; c < 26; c++) {
        if (trie[0][c]) {
            fail[trie[0][c]] = 0;
            q.push(trie[0][c]);
        }
    }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo.push_back(u);
        for (int c = 0; c < 26; c++) {
            int v = trie[u][c];
            if (v) {
                int f = fail[u];
                while (f && !trie[f][c]) f = fail[f];
                fail[v] = trie[f][c];
                in[fail[v]]++;
                q.push(v);
            }
        }
    }
    // 逆拓扑累加后缀答案
    for (auto it = topo.rbegin(); it != topo.rend(); it++) {
        int u = *it;
        endpos[fail[u]] += endpos[u];
    }
}

// 查询简化，无需循环fail链
int query_opt(const string &s) {
    int u = 0, res = 0;
    for (char ch : s) {
        int c = ch - 'a';
        while (u && !trie[u][c]) u = fail[u];
        u = trie[u][c];
        res += endpos[u];
    }
    return res;
}

六、分步使用方法（做题标准流程）

步骤 1：初始化

调用init()清空 Trie、fail、计数、节点编号。

步骤 2：插入全部模式串

循环读入每个模式串，insert(s)插入 Trie 树。

步骤 3：构建失配指针

• 普通版：build()
• 大数据（1e5+）：build_opt()拓扑优化版

步骤 4：读入文本，查询

• 普通：query(text)
• 优化：query_opt(text) 返回值为文本中所有模式串出现总次数。

七、关键概念对比 KMP vs AC 自动机

1. KMP：单个模式串匹配，next 数组；
2. AC 自动机：多模式串批量匹配，Trie 存所有串，fail 数组是树上版 next；
3. fail 指针本质：树上每个节点的最长后缀对应节点，等价于 KMP 的最长 border。

八、常见题型

1. 基础：统计文本出现多少个模式串；
2. 标记每个串是否出现；
3. 求出现次数最多的模式串；
4. 矩阵加速 AC 自动机（数位 DP、字符串 DP）；
5. 病毒匹配（文本不能包含任意病毒串）。

九、补充小细节

1. 数组开1e6+10够用，多组数据必须memset初始化；
2. 只小写字母，字符映射ch-'a'；大写 / 数字扩展只需改映射；
3. 若模式串去重：插入前判断是否已存在，或插入后不去重，endpos 自动计数；
4. 查询时u=0是根节点，代表无匹配。