Lesson 58: AC自动机 — Aho-Corasick 多模式匹动机

练习任务

难度：中

实现 Aho-Corasick (AC 自动机) 多模式字符串匹配算法，在固定模式集 {"he", "she", "his", "hers"} 和文本 "ushers" 上运行。你需要完成六个核心函数：

new_node() — 创建新 Trie 节点，初始化 children/fail/output
insert() — 将模式串插入 Trie 树
bfs_build_fail() — BFS 层序遍历构建失败链接 (Failure Link)
print_trie() — 打印每个节点的子节点、失败链接、输出模式
search() — 扫描文本，逐步输出状态转移和匹配结果
补全 main() — 串联上述步骤并输出最终匹配汇总

字母表固定为 a-z（26 个小写字母），节点数不超过 30。

验证方式: make test
        编译程序后运行，通过管道 | diff 比对预期输出

TIP

AC 自动机的核心洞察：将多个模式串的 Trie 树升级为确定性有限自动机 (DFA)。失败链接使得每个状态在任何输入字符下都有确定的下一个状态——要么沿 children 前进，要么沿 fail 链回退寻找，要么回到根。KMP 是"一根线上的回退"，AC 自动机是"一棵树上的回退"。

核心知识点

Trie 树的数组实现 — 每个节点用 children[26] 固定数组存储子节点索引，-1 表示无此子节点，O(1) 查找
失败链接 = KMP 前缀函数的 Trie 推广 — 对节点 v 表示的前缀，fail[v] 指向其最长真后缀同时也是某个模式前缀的节点
BFS 构建失败链接的必要性 — 子节点的 fail 依赖父节节点的 fail，BFS 保证处理子节点前父节点 fail 已就绪；DFS 会先访问深层节点导致错误
输出合并机制 — 将失败链接上的输出累积到当前节点，实现一次扫描发现所有匹配（含嵌套/重叠模式）
search() 中沿 fail 链状态转移 — 当前字符不匹配时沿 fail 链逐步回退而非直接回根，充分利用已匹配信息
匹配位置计算 — start = i - strlen(pattern) + 1，其中 i 是文本中当前字符索引
O(n + M + z) 时间复杂度 — n=文本长度, M=所有模式总长度, z=匹配数量，对比暴力 O(k×n×m) 优势显著

代码框架

58_aho_corasick.c

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHABET 26
#define MAX_NODES 30
#define MAX_PATTERNS 4
#define MAX_PAT_LEN 10

/* Trie 节点：children[26] = 子节点索引(-1=无), fail = 失败链接 */
typedef struct {
    int children[ALPHABET];
    int fail;
    int output_count;
    char outputs[MAX_PATTERNS][MAX_PAT_LEN];
} TrieNode;

static TrieNode nodes[MAX_NODES];
static int node_count = 0;

/* ─── TODO 1: 创建新节点 ─── */
static int new_node(void) {
    // ① 保存当局: node_count 作为新节点索引，node_count++
    // ② 将 children[0..25] 全部初始化为 -1
    // ③ fail 初始化为 0
    // ④ output_count 初始化为 0
    // ⑤ 返回新节点索引
}

/* ─── TODO 2: 插入模式串到 Trie ─── */
static void insert(const char *pattern) {
    // ① 从根节点 cur=0 开始
    // ② 遍历 pattern 每个字符: c = ch - 'a'
    //    若 children[c] == -1，调用 new_node() 创建子节点
    //    cur = children[c] 进入下一层
    // ③ 遍历结束后在 cur 节点记录输出:
    //    将 pattern 复制到 outputs[output_count]，output_count++
}

/* ─── TODO 3: BFS 构建失败链接 ─── */
static void bfs_build_fail(void) {
    // ① 准备队列 queue[MAX_NODES], head=0, tail=0
    // ② 根节点(0)的直接子节点入队，fail 设为 0
    // ③ BFS 主循环: while head < tail
    //    - 弹出 cur = queue[head++]
    //    - 遍历 cur 的 26 个子节点 child
    //    - 计算 child.fail: 沿 cur.fail 链找有同字符子节点的祖先
    //    - 输出合并: 将 fail_node 的 outputs 追加到 child
    //    - child 入队
}

/* ─── TODO 4: 打印 Trie 结构 ──── */
static void print_trie(void) {
    // 遍历所有节点, 打印 children(跳过-1)、fail、output
}

/* ─── TODO 5: 扫描文本 ─── */
static void search(const char *text) {
    // ① cur=0, 逐个字符扫描
    // ② 若 children[c]==-1，沿 fail[cur] 回退
    // ③ 匹配成功则 cur=children[c]
    // ④ 检查 outputs: 若有匹配, 打印模式名和起始位置
    //    起始位置 = i - strlen(模式名) + 1
}

/* ──── TODO 6: main() 主流程 ─── */
int main(void) {
    // ① new_node() 初始化根节点
    // ② insert("he"), insert("she"), insert("his"), insert("hers")
    // ③ bfs_build_fail()
    // ④ print_trie()
    // ⑤ search("ushers")
    // ⑥ 最终匹配汇总输出
    return 0;
}

阅读骨架后，尝试自己填充 TODO 1 ~ TODO 6 标记的部分。核心挑战在于：children[] 为什么用 -1 而不用 0 表示"无子节点"5 BFS 构建失败链接的三层嵌套逻辑（cur → child → fail chain）如何理解？输出合并为什么必不可少？search() 中匹配失败时如何沿 fail 链回退？

TIP

先不要往下翻看参考解答。用模式集 {"he", "she", "his", "hers"} 在纸上画出完整的 Trie 树（10 个节点），标注每条 failed link 的指向和原因。然后手动追踪文本 "ushers" 的每一步状态转移。

深度讲解

1. Trie 树结构与 insert() 机制 — 前缀的物理存储

1.1 为什么用数组而非指针？

AC 自动机中每个 Trie 节点需要快速找到"下一个字符对应的子节点"。本题字母表固定为 a-z（26 个字符），直接用数组 children[26] 实现 O(1) 查找。

trie_node.c

typedef struct {
    int children[26];   // 下标 = 字符-'a'，值 = 子节点索引
    int fail;           // 失败链接目标节点索引
    int output_count;
    char outputs[4][10]; // 输出模式名
} TrieNode;

节点索引映射:

  children[c] = -1  → 无此子节点（关键！不能用 0，因为 0 是根节点）
  children[c] = k   → 存在子节点，索引为 k

  fail = j          → 匹配失败跳转到节点 j
  output_count = n  → 该节点有 n 个输出模式

CAUTION

初学者最易犯的错误之一：用 0 表示"无子节点"。这会导致 children[0] 指向根节点（索引 0），产生错误的跳转。正确做法是用 -1 作为哨兵值，与有效节点索引（0, 1, 2, ...）明确区分。

1.2 本题 Trie 树完整结构

将 4 个模式 {"he", "she", "his", "hers"} 插入 Trie 后的结构（共 10 个节点，索引 0~9）：

                    ┌───────────────────────┐
                    │        Node 0          │
                    │      (root, "")        │
                    │  children: h→1, s→3    │
                    │  fail: 0               │
                    └───────┬───┬───────────┘
                           /     \
                      h  /       \  s
                         /         \
          ┌──────────────┐      ┌──────────────┐
          │   Node 1     │      │   Node 3     │
          │   ("h")      │      │   ("s")      │
          │ children:    │      │ children:    │
          │   e→2, i→6   │      │   h→4        │
          │ fail: 0      │      │ fail: 0      │
          └──┬────┬──────┘      └──────┬───────┘
            /      \                   /
       e  /        \  i           h  /
         /          \               /
┌──────────┐   ┌──────────┐   ┌──────────┐
│ Node 2   │   │ Node 6   │   │ Node 4   │
│ ("he")   │   │ ("hi")   │   │ ("sh")   │
│ child:   │   │ child:   │   │ child:   │
│  r→8     │   │  s→7     │   │  e→5     │
│ fail: 0  │   │ fail: 0  │   │ fail: 1  │
│out:["he"]│   │          │   │          │
└──┬───────┘   └──┬───────┘   └──┬────────┘
   |              |              |
r  |           s  |           e  |
   |              |              |
┌──────────┐   ┌──────────┐   ┌──────────────┐
│ Node 8   │   │ Node 7   │   │   Node 5     │
│ ("her")  │   │ ("his")  │   │  ("she")     │
│ child:   │   │ children:│   │ children: {} │
│  s→9     │   │  {}      │   │ fail: 2      │
│ fail: 0  │   │ fail: 3  │   │out:["she",   │
└──┬───────┘   │out:["his"]│   │     "he"]    │
   |           └──────────┘   └──────────────┘
s  |
   |
┌──────────┐
│ Node 9   │
│ ("hers") │
│ children:│
│  {}      │
│ fail: 3  │
│out:["hers"]│
└──────────┘

关键观察:
  - Node 4 ("sh") 的 fail=1 ("h") — "sh" 的最长真后缀是 "h"，且 "h" 在 Trie 中
  - Node 5 ("she") 的 fail=2 ("he") — "she" 的最长真后缀是 "he"，且 "he" 在 Trie 中
  - Node 7 ("his") 的 fail=3 ("s") — "his" 的最长真后缀是 "s"，而 "s" 在 Trie 中
  - Node 9 ("hers") 的 fail=3 ("s") — "hers" 的最长真后缀是 "s"，而 "s" 在 Trie 中
  - Node 5 的输出 = ["she", "he"] — 通过输出合并累积了 fail[5]=2 的 "he"

1.3 insert() 逐步演示

insert_trace.c

void insert(const char *pattern) {
    int cur = 0;                      // 从根节点开始
    for (int i = 0; pattern[i]; i++) {
        int c = pattern[i] - 'a';     // 字符转索引 (0-25)
        if (nodes[cur].children[c] == -1)
            nodes[cur].children[c] = new_node();
        cur = nodes[cur].children[c]; // 进入下一层
    }
    // 在终止节点记录输出
    int oc = nodes[cur].output_count;
    strcpy(nodes[cur].outputs[oc], pattern);
    nodes[cur].output_count++;
}

以 insert("she") 为例：

insert("she"):

  cur=0, 字符 's' (c=18):
    nodes[0].children[18] == -1  →  new_node() 创建 Node 3
    nodes[0].children[18] = 3
    cur = 3

  cur=3, 字符 'h' (c=7):
    nodes[3].children[7] == -1  →  new_node() 创建 Node 4
    nodes[3].children[7] = 4
    cur = 4

  cur=4, 字符 'e' (c=4):
    nodes[4].children[4] == -1  →  new_node() 创建 Node 5
    nodes[4].children[4] = 5
    cur = 5

  循环结束，cur=5:
    nodes[5].outputs[0] = "she"
    nodes[5].output_count = 1

NOTE

注意：insert() 只负责构建 Trie 树——不设置失败链接，不进行输出合并。失败链接是后续通过 bfs_build_fail() 统一构建的。

2. 失败链接 — KMP 前缀函数的 Trie 推广

2.1 从 KMP 到 AC 自动机

KMP 单模式匹配:
  模式 "abab"
  前缀函数 π = [0, 0, 1, 2]
  匹配失败时：j = π[j-1]  ← 回退到此前缀的最长真后缀长度位置

AC 自动机多模式匹配:
  模式集 {"he", "she", "his", "hers"}
  失败链接 fail[v] = k  ← 节点 v 表示的前缀的最长真后缀（也是某模式前缀）
                        对应的 Trie 节点索引

失败链接的核心定义：对于 Trie 中的每个节点 v，fail[v] 指向另一个节点 f，使得 f 表示的前前缀是 v 表示的前缀的最长真后缀（同时也是某个模式的前缀）。

2.2 失败链接的三个关键性质

性质 1: 根节点的 fail = 0 (自身)
性质 2: 根节点的所有直接子节点的 fail = 0 (根)
性质 3: 对于节点 v (父节点 u, 边字符 c):
         从 f = fail[u] 开始，沿 fail 链向上寻找第一个有 c 子节点的节点 f'
         如果找到: fail[v] = nodes[f'].children[c]
         否则:    fail[v] = 0

直观理解:
  当前已匹配到节点 v 表示的前缀 P。
  假设下一个字符不匹配 → 我们不想从头开始。
  问： P 的「最长真后缀」中，哪个还是某个模式的前缀？
  答案: fail[v] 表示的前缀。

  失败链接 = "匹配失败时的最佳回退点"。
  与 KMP 的差异: KMP 回退到同一模式的位置，AC 回退到可能不同的模式。

2.3 失败链接的具体含义解读

以本题为例:

┌──────┬─────────────┬──────┬──────────────────────────────────────┐
│ Node │  表示的前缀  │ fail │  含义                                │
├───────┼─────────────┼──────┼──────────────────────────────────────┤
│  4   │   "sh"      │  1   │ "sh" 的最长真后缀 "h" 是前缀 "…h"    │
│      │             │      │ 对应的节点，即 Node 1                  │
│  5   │   "she"     │  2   │ "she" 的最长真后缀 "he" 是模式 "he"   │
│      │             │      │ 对应的节点 Node 2                      │
│  7   │   "his"     │  3   │ "his" 的最长真后缀 "s" 是前缀 "…s"    │
│      │             │      │ 对应的节点 Node 3                      │
│  9   │   "hers"    │  3   │ "hers" 的最长真后缀 "s" 是前缀 "…s"   │
│      │             │      │ 对应的节点 Node 3                      │
└──────┴─────────────┴──────┴──────────────────────────────────────┘

3. BFS 构建失败链接 — 逐层推演

3.1 为什么必须用 BFS？

BFS vs DFS 在构建 fail 时的区别:

  BFS (正确):
    处理顺序: 0 → 1, 3 → 2, 6, 4 → 8, 7, 5 → 9
    当处理 Node 5 (深度 3) 时，Node 1 (深度 1) 和 Node 2 (深度 2) 的 fail 已就绪
    → fail[4]=1, fail[2]=0 已计算 → 可以正确计算 fail[5]=2 ✓

  DFS (错误):
    可能路径: 0 → 1 → 2 → 8 → 9 (深度 4)
    处理 Node 9 时 fail[8] 刚计算完，但 fail[3] 可能还未计算
    点的 fail[9] 依赖 fail[8] 的 fail 链查找 → 如果 fail[3] 未就绪 → 错误 ✗

IMPORTANT

失败链接存在严格的层级依赖：fail[v] 依赖 fail[parent(v)]。BFS 保证处理深度为 d 的节点时，所有深度 < d 的节点的 fail 都已计算完毕。这是算法的正确性前提，不是性能优化。

3.2 完整 BFS 构建过程追踪

bfs_build_fail.c

static void bfs_build_fail(void) {
    int queue[MAX_NODES], head = 0, tail = 0;

    // 第一阶段: 根节点的直接子节点入队，fail = 0
    for (int c = 0; c < ALPHABET; c++) {
        int child = nodes[0].children[c];
        if (child != -1) {
            nodes[child].fail = 0;
            queue[tail++] = child;
        }
    }

    // 第二阶段: BFS 主循环
    while (head < tail) {
        int cur = queue[head++];

        for (int c = 0; c < ALPHABET; c++) {
            int child = nodes[cur].children[c];
            if (child == -1) continue;

            // 计算 child 的 fail: 沿 cur.fail 链向上寻找
            int f = nodes[cur].fail;
            while (f != 0 && nodes[f].children[c] == -1)
                f = nodes[f].fail;
            if (nodes[f].children[c] != -1 && nodes[f].children[c] != child)
                nodes[child].fail = nodes[f].children[c];
            else
                nodes[child].fail = 0;

            // 输出合并: 把 fail 节点的 outputs 复制到 child
            int fail_node = nodes[child].fail;
            for (int i = 0; i < nodes[fail_node].output_count; i++) {
                strcpy(nodes[child].outputs[nodes[child].output_count],
                       nodes[fail_node].outputs[i]);
                nodes[child].output_count++;
            }

            queue[tail++] = child;
        }
    }
}

BFS 构建过程精简如下：

Step 1: 根子节点入队 → queue=[1,3], fail[1]=fail[3]=0
Step 2: pop 1("h") → child 2: 0无'e'→fail[2]=0; child 6: 0无'i'→fail[6]=0
Step 3: pop 3("s") → child 4: 0有'h'→1→fail[4]=1 (第一个非根 fail!)
Step 4: pop 2("he")→ child 8: 0无'r'→fail[8]=0
Step 5: pop 6("hi")→ child 7: 0有's'→3→fail[7]=3
Step 6: pop 4("sh")→ child 5: fail[4]=1有'e'→2→fail[5]=2
         输出合并: Node 5 outputs=["she","he"] ← 关键!
Step 7: pop 8("her")→ child 9: 0有's'→3→fail[9]=3
Steps 8-10: 队空, BFS 结束

IMPORTANT

Step 6 是理解 AC 自动机的关键步骤。Node 5（对应 "she"）的输出从 ["she"] 变为 ["she", "he"]。这就是输出合并：当文本匹配到 "she" 时，同时也匹配到了 "he"（因为 "he" 是 "she" 的后缀）。输出合并使得一次扫描即可发现所有匹配，无需回退。

4. search() 扫描过程 — 状态转移的完整追踪

4.1 核心算法

search.c

static void search(const char *text) {
    int cur = 0;
    printf("=== Scanning: \"%s\" ===\n", text);

    for (int i = 0; text[i]; i++) {
        int c = text[i] - 'a';

        // 沿 fail 链回退直到找到匹配或回到根
        while (cur != 0 && nodes[cur].children[c] == -1)
            cur = nodes[cur].fail;

        // 匹配成功，前进
        if (nodes[cur].children[c] != -1)
            cur = nodes[cur].children[c];

        printf("Step %d: char='%c' -> node %d", i, text[i], cur);

        // 打印所有匹配
        for (int j = 0; j < nodes[cur].output_count; j++) {
            char *pat = nodes[cur].outputs[j];
            int start = i - (int)strlen(pat) + 1;
            printf(" [match: %s@%d]", pat, start);
        }
        printf("\n");
    }
}

4.2 文本 "ushers" 完整追踪

Step 0: u → cur=0(无子u) → 输出: 无
Step 1: s → cur=3(Node 3)
Step 2: h → cur=4(Node 4)
Step 3: e → cur=5(Node 5) → 输出: she@1, he@2 (输出合并!)
Step 4: r → cur=5无子r, 沿fail[5]=2→2有子r=8 → cur=8
Step 5: s → cur=9 → 输出: hers@2

最终匹配: "she"@1, "he"@2, "hers"@2

NOTE

search() 中 while (cur != 0 && nodes[cur].children[c] == -1) 的 cur != 0 条件很重要：当回退到根节点时停止。cur=0 表示"从头开始"。失败链接跳转(Step 4)和输出合并(Step 3)是核心机制。

5. 复杂度分析与工程要点

5.1 时间复杂度

算法	预处理	匹配 (k 个模式)	总计
暴力匹配	O(1)	O(k × n × m)	O(k × n × m)
KMP × k	O(k × m)	O(k × n)	O(k × (n + m))
AC 自动机	O(M × σ)	O(n + z)	O(M×σ + n + z)

其中：n = 文本长度，m = 单个模式平均长度，M = 所有模式模式长度，σ = 字母表大小 (26)，z = 匹配总数，k = 模式数量。

5.2 空间复杂度

Trie 节点: 每个节点 ≈ 26×4(children) + 4(fail) + 4(count) + 40(outputs) ≈ 152 字节
本题最多 30 个节点 → 30×152 ≈ 4.5KB

若模式数量极大 (百万级):
  - 双数组 Trie (Double-Array Trie) 可压缩 10-100 倍
  - 压缩 AC 自动机合并单分支路径
  - 分块策略: 多个小 AC 自动机并行匹配

5.3 常见错误

错误	后果	正确做法
`children[]` 用 0 表示"无子节点"	混淆根节点(0)与"无子节点"，导致错误跳转	用 -1 表示"无子节点"
失败链接用 DFS 而非 BFS	深层节点可能引用未计算的 fail	必须用 BFS 队列层序遍历
`search()` 匹匹配失败直接回根	漏掉中间状态的匹配	沿 fail 链逐步回退，不直接跳根
忘记合并 fail 链上的输出	漏报匹配（如本题漏掉 "he"）	`bfs_build_fail()` 中显式复制 outputs
匹配位置计算错误	输出错误的起始位置	`start = i - strlen(pattern) + 1`
`fail` 初始化为 -1	BFS 时访问 `nodes[-1]` → 段错误	`fail` 初始化为 0
循环变量用 `unsigned` 类型	与 `strlen` 比较时可能下溢	用 `int` 或 `size_t` 并注意比较

参考解答

TODO 1-2: new_node() + insert() — 构建 Trie 树

solution_58_new_node_insert.c

#include <string.h>
#include <stdbool.h>

#define ALPHABET 26
#define MAX_NODES 30
#define MAX_PATTERNS 4
#define MAX_PAT_LEN 10

typedef struct {
    int children[ALPHABET];
    int fail;
    int output_count;
    char outputs[MAX_PATTERNS][MAX_PAT_LEN];
} TrieNode;

static TrieNode nodes[MAX_NODES];
static int node_count = 0;

/* new_node: 创建新 Trie 节点并返回索引 */
static int new_node(void) {
    int idx = node_count;
    node_count++;
    for (int i = 0; i < ALPHABET; i++)
        nodes[idx].children[i] = -1;
    nodes[idx].fail = 0;
    nodes[idx].output_count = 0;
    return idx;
}

/* insert: 将模式串插入 Trie 树 */
static void insert(const char *pattern) {
    int cur = 0;
    for (int i = 0; pattern[i]; i++) {
        int c = pattern[i] - 'a';
        if (nodes[cur].children[c] == -1)
            nodes[cur].children[c] = new_node();
        cur = nodes[cur].children[c];
    }
    int oc = nodes[cur].output_count;
    strcpy(nodes[cur].outputs[oc], pattern);
    nodes[cur].output_count++;
}

要点：

new_node() 返回 node_count 的旧值，然后自增（node_count++）
children[] 全部初始化为 -1（不是 0）
outputs[] 记录模式名的副本（strcpy），不是指针

TODO 3: bfs_build_fail() — BFS 构建失败链接

solution_58_bfs_build_fail.c

/* bfs_build_fail: BFS 层序遍历构建失败链接 */
static void bfs_build_fail(void) {
    int queue[MAX_NODES], head = 0, tail = 0;

    /* 根的直接子节点入队 */
    for (int c = 0; c < ALPHABET; c++) {
        int child = nodes[0].children[c];
        if (child != -1) {
            nodes[child].fail = 0;
            queue[tail++] = child;
        }
    }

    /* BFS 主循环 */
    while (head < tail) {
        int cur = queue[head++];

        for (int c = 0; c < ALPHABET; c++) {
            int child = nodes[cur].children[c];
            if (child == -1) continue;

            /* 计算 child 的 fail: 沿 cur.fail 链向上找 */
            int f = nodes[cur].fail;
            while (f != 0 && nodes[f].children[c] == -1)
                f = nodes[f].fail;
            if (nodes[f].children[c] != -1 && nodes[f].children[c] != child)
                nodes[child].fail = nodes[f].children[c];
            else
                nodes[child].fail = 0;

            /* 输出合并: 把 fail 节点的 outputs 复制到 child */
            int fail_node = nodes[child].fail;
            for (int i = 0; i < nodes[fail_node].output_count; i++) {
                /* 注意：检查越界 */
                int oc = nodes[child].output_count;
                strcpy(nodes[child].outputs[oc], nodes[fail_node].outputs[i]);
                nodes[child].output_count++;
            }

            queue[tail++] = child;
        }
    }
}

要点：

三个阶段：根的直接子节点入队 → BFS 遍历 → 对每个 child 计算 fail 并合并输出
fail 查找的 while 条件是 f != 0，不是 f != -1
输出合并时 nodes[f].children[c] != child 防止自己指向自己

TODO 4-5: print_trie() + search() — 打印和扫描

solution_58_print_search.c

/* print_trie: 打印每个节点的结构信息 */
static void print_trie(void) {
    printf("=== Trie Structure ===\n");
    printf("Total nodes: %d\n\n", node_count);

    for (int i = 0; i < node_count; i++) {
        printf("Node %d: children={", i);
        int first = 1;
        for (int c = 0; c < ALPHABET; c++) {
            if (nodes[i].children[c] != -1) {
                if (!first) printf(", ");
                printf("'%c'->%d", c + 'a', nodes[i].children[c]);
                first = 0;
            }
        }
        printf("} fail=%d", nodes[i].fail);

        if (nodes[i].output_count > 0) {
            printf(" output=[");
            for (int j = 0; j < nodes[i].output_count; j++) {
                if (j > 0) printf(", ");
                printf("\"%s\"", nodes[i].outputs[j]);
            }
            printf("]");
        }
        printf("\n");
    }
    printf("\n");
}

/* search: 扫描文本，输出每一步状态和匹配 */
static void search(const char *text) {
    int cur = 0;
    printf("=== Scanning: \"%s\" ===\n", text);

    for (int i = 0; text[i]; i++) {
        int c = text[i] - 'a';

        /* 沿 fail 链找到匹配路径 */
        while (cur != 0 && nodes[cur].children[c] == -1)
            cur = nodes[cur].fail;

        if (nodes[cur].children[c] != -1)
            cur = nodes[cur].children[c];

        printf("Step %d: char='%c' -> node %d", i, text[i], cur);

        /* 打印所有匹配 */
        for (int j = 0; j < nodes[cur].output_count; j++) {
            char *pat = nodes[cur].outputs[j];
            int start = i - (int)strlen(pat) + 1;
            printf(" [match: %s@%d]", pat, start);
        }
        printf("\n");
    }
    printf("\n");
}

要点：

print_trie() 跳过 children[c] == -1 的子节点（仅打印有效子节点）
search() 中输出匹配时用 strlen(pat) 计算起始位置：i - len + 1
注意 strlen 返回 size_t，减法前转为 int 避免无符号下溢

TODO 6: main() — 完整主流程

solution_58_main.c

int main(void) {
    node_count = 0;
    new_node();  /* 初始化根节点 (索引 0) */

    /* 插入 4 个模式串 */
    insert("he");
    insert("she");
    insert("his");
    insert("hers");

    /* 构建失败链接 */
    bfs_build_fail();

    /* 打印 Trie 结构 */
    print_trie();

    /* 扫描文本 */
    search("ushers");

    /* 最终匹配汇总 */
    printf("=== Final Matches ===\n");

    /* 重新扫描并汇总 (或直接输出已知结果) */
    int cur = 0;
    const char *text = "ushers";
    for (int i = 0; text[i]; i++) {
        int c = text[i] - 'a';
        while (cur != 0 && nodes[cur].children[c] == -1)
            cur = nodes[cur].fail;
        if (nodes[cur].children[c] != -1)
            cur = nodes[cur].children[c];
        for (int j = 0; j < nodes[cur].output_count; j++) {
            char *pat = nodes[cur].outputs[j];
            int start = i - (int)strlen(pat) + 1;
            int end = i;
            printf("Pattern \"%s\" found at position %d (ending at %d)\n",
                   pat, start, end);
        }
    }

    return 0;
}

核心逻辑解析：

构建阶段：new_node() → insert() × 4 → bfs_build_fail() 构建完整 AC 自动机
输出阶段：print_trie() 展示结构 → search() 展示扫描过程
汇总阶段：再次扫描文本，输出每个匹配的模式名、起始位置、结束位置

对照检查：new_node() 中 children 初始化为 -1 了吗？bfs_build_fail() 中输出合并且检查越界了吗？search() 中匹配位置计算公式正确吗（i - len + 1）？main() 中书输出格式匹配 expected_output.txt 了吗？

课堂讨论

为什么失败链接构建必须用 BFS 而不能用 DFS？如果强行用 DFS 会有什么后果？
如果所有模式串之间没有重叠（如 {"abc", "def", "ghi"}），失败链接的结果会是什么样？输出合并还有意义吗？
本题用固定大小数组 children[26] 存储子节点。如果字母表扩展到 Unicode (百万字符)，应该怎么改？
AC 自动机与 KMP 的本质关系是什么？能否说 "AC 自动机 = Trie + KMP"？
如果把文本换成 "hishers"，会匹配到什么？AC 自动机在一次扫描中能发现多少个匹配（包括重叠和嵌套）？

讨论答案

Q1: 为什么必须用 BFS？

fail[v] 依赖 fail[parent(v)]，BFS 保证处理深度 d 的节点时所有浅层 fail 已就绪。本接用 DFS 路径 0→1→2→8→9 会导致处理 Node 9 时 fail[3] 未计算，产生错误。

Q2: 无重叠模式的失败链接？

模式集 {"abc","def","ghi"} 无前缀重叠 → 所有 fail 指向 0（根），输出合并无效。AC 自动机退化为多路独立 Trie 查找，但算法仍然正确。

Q3: 大字母表的存储方案？

哈希表代替固定数组：空间与子节点数成比例
双数组 Trie (Double-Array Trie)：压缩 10-100 倍，如 MeCab 中文分词

Q4: AC 自动机与 KMP 的关系？

KMP = 只有一个模式时的 AC 自动机 = 单链 Trie 上的失败链接。AC = 多链 Trie 上的推广。"AC = Trie + KMP" 基本正确，但"+"是"推广"而非"并列"——失败链接是前缀函数在多前缀场景的自然拓展。

Q5: "hishers" 的匹配？

一次扫描发现 4 个匹配："his"@0, "she"@1, "he"@2, "hers"@3。展示了重叠/嵌套模式的同时匹配能力。

课后练习

反向文本扫描。修改 search() 从文本末尾向开头扫描。AC 的失败链接依赖"前缀→后缀"关系，反向扫描需"后缀→前缀"关系，需构建反向 Trie 或使用后缀自动机 (SAM)。
参考解答
结论：直接反向扫描不能复用原 AC 自动机，需将模式串反序后重新构建。
统计每个模式的匹配次数。在 search() 中维护 match_count[] 数组，匹配到时递增。模式名到索引的映射通过插入顺序确定。
参考解答
验证 AC 自动机的 DFA 性质。预计算 goto_table[state][c] — 加入失败链接后每个状态对 26 个字符都有确定的下一个状态，AC 自动机是一个完全 DFA。
参考解答

与已有课程的联系

课程	关联知识点
Lesson 25 `my_strstr`	暴力单模式匹配 — AC 自动机的基础对比
Lesson 35 `queue_base`	队列数据结构 — BFS 构建 fail 的基础
Lesson 36 `binary_tree_traversal`	BFS 层序遍历 — 与 fail 构建的 BFS 一致
Lesson 40 `binary_search`	搜索空间缩小 — 与 fail 链的"跳转"思想类似
Lesson 51 `ll1-table-parser`	确定性有限自动机 (DFA) — AC 自动机是 DFA 的一种
Lesson 39 `heap-base-topk`	算法复杂度分析 — O(n) vs O(n log n) 的证明方法

参考资料

Aho, A. V., & Corasick, M. J. (1975). "Efficient String Matching: An Aid to Bibliographic Search". Communications of the ACM, 18(6), 333–340.
Crochemore, M., & Rytter, W. (1994). Text Algorithms. Oxford University Press. Chapter 3.
Gusfield, D. (1997). Algorithms on Strings, Trees, and Sequences. Cambridge University Press. Chapter 3.4.
man 3 strcpy, man 3 strlen — C 标准库字符串函数
CP-Algorithms — Aho-Corasick — 算法详解与实现

"AC 自动机的优雅之处在于：它将 KMP 的单线回退推广到 Trie 的树上回退，用 BFS 保证了层级依赖的正确性，用输出合并实现了真正的一次扫描发现所有匹配。"

Lesson 58: AC自动机 — Aho-Corasick 多模式匹动机 ​

练习任务 ​

核心知识点 ​

代码框架 ​

深度讲解 ​

1. Trie 树结构与 insert() 机制 — 前缀的物理存储 ​

1.1 为什么用数组而非指针？ ​

1.2 本题 Trie 树完整结构 ​

1.3 insert() 逐步演示 ​

2. 失败链接 — KMP 前缀函数的 Trie 推广 ​

2.1 从 KMP 到 AC 自动机 ​

2.2 失败链接的三个关键性质 ​

2.3 失败链接的具体含义解读 ​

3. BFS 构建失败链接 — 逐层推演 ​

3.1 为什么必须用 BFS？ ​

3.2 完整 BFS 构建过程追踪 ​

4. search() 扫描过程 — 状态转移的完整追踪 ​

4.1 核心算法 ​

4.2 文本 "ushers" 完整追踪 ​

4.2 文本 "ushers" 完整追踪 ​

5. 复杂度分析与工程要点 ​

5.1 时间复杂度 ​

5.2 空间复杂度 ​

5.3 常见错误 ​

参考解答 ​

课堂讨论 ​

讨论答案 ​

讨论答案 ​

课后练习 ​

与已有课程的联系 ​

参考资料 ​

Lesson 58: AC自动机 — Aho-Corasick 多模式匹动机

练习任务

核心知识点

代码框架

深度讲解

1. Trie 树结构与 insert() 机制 — 前缀的物理存储

1.1 为什么用数组而非指针？

1.2 本题 Trie 树完整结构

1.3 insert() 逐步演示

2. 失败链接 — KMP 前缀函数的 Trie 推广

2.1 从 KMP 到 AC 自动机

2.2 失败链接的三个关键性质

2.3 失败链接的具体含义解读

3. BFS 构建失败链接 — 逐层推演

3.1 为什么必须用 BFS？

3.2 完整 BFS 构建过程追踪

4. search() 扫描过程 — 状态转移的完整追踪

4.1 核心算法

4.2 文本 "ushers" 完整追踪

4.2 文本 "ushers" 完整追踪

5. 复杂度分析与工程要点

5.1 时间复杂度

5.2 空间复杂度

5.3 常见错误

参考解答

课堂讨论

讨论答案

讨论答案

课后练习

与已有课程的联系

参考资料