题干与适用场景
这是日志过滤、敏感词检测或编辑器高亮中常见的多模式匹配题。设关键词总长度为 M，文本长度为 N，要求报告每个匹配的起点和关键词编号。关键词在构建阶段固定，文本可能很长，面试官希望你说明预处理、扫描复杂度和重复匹配如何处理。
面试官考察点
面试官考察你能否把 Trie 的前缀复用扩展为有限状态机。强回答会构建失败链接、沿失败链继承输出，并解释每个字符只触发有限次状态转移；普通回答只说“用 Trie 搜索”，却无法处理后缀重叠或失配回退。
回答前需要澄清的问题
- 是否区分大小写、Unicode 规范化或字节？字符定义会改变 Trie 和位置单位。
- 是否需要返回重叠匹配和同一结束位置的多个关键词？这决定输出链是否完整。
- 关键词是否会频繁更新？静态词典适合构建自动机，动态词典可能需要分块重建。
- 位置按字符、字节还是 UTF-16 code unit 计数？必须与调用方契约一致。
- 文本是否分块到达？跨块扫描要保留当前状态，不能每块重置。
30 秒回答框架
“我先把关键词插入 Trie，再用 BFS 为每个节点建立失败链接：它表示当前前缀失配后最长的可用后缀。每个节点合并自身和失败节点的输出列表。扫描文本时沿转移或失败链接移动，并报告当前节点输出。构建复杂度与关键词总长度和边数线性相关，扫描为 O(N + 匹配数)，流式分块只需保留状态。”
分步骤深入解答
- 建立 Trie。 每个节点保存子边、失败链接和输出的关键词编号；关键词结束节点追加编号，不能只保存一个。
- 初始化失败链接。 根节点的直接子节点失败链接指向根；用队列按深度处理其余节点。
- 计算失败转移。 对节点的字符边，沿父节点失败链接寻找同字符边；找不到就回到根。这样扫描时无需重新比较文本字符。
- 聚合输出。 将失败目标的输出追加到当前节点，或保存输出链接以节省复制；后者要在查询时沿链遍历。
- 扫描文本。 每个字符先尝试子边，失配就沿失败链接，直到找到边或回到根；进入节点后报告全部输出，位置由当前索引减关键词长度加一得到。
- 处理边界。 重叠关键词自然会同时输出；分块输入保留状态。若输出量巨大，应支持回调、上限或分页，避免把 O(匹配数) 结果一次性放入内存。
一个简单实现可把字符到子节点的映射设为哈希表；固定小字母表可用数组换取更快转移。若关键词动态变化，按词典版本构建新自动机并原子切换，避免扫描过程看到半成品。
高质量示范回答
“我会先插入所有关键词并记录每个终点的编号，然后 BFS 计算失败链接。根的孩子失败到根；其他边沿父节点失败链寻找同字符转移，找不到就回根。节点输出包含自身终点和失败节点输出，因此 he 与 she 在扫描 she 时都会报告。扫描每个字符只沿子边或失败链接移动，复杂度是 O(N + Z)，Z 是匹配数量；预处理是 O(M) 加上边表示的开销。文本分块时保留状态，词典更新则构建新版本后切换。”
常见错误
- 错误表现： 失配后把指针和文本一起回退 → 失败原因： 退化为每个关键词重复扫描 → 修正方法： 使用失败链接保持文本索引单调前进。
- 错误表现： 每个节点只保留一个输出 → 失败原因： 后缀关键词和重复终点会丢失 → 修正方法： 合并失败链输出或维护输出链接。
- 错误表现： 认为扫描一定是 O(N) → 失败原因： 输出匹配本身可能达到 O(Z) → 修正方法： 明确报告 O(N + Z) 并设计流式输出。
- 错误表现： 分块处理时重置根状态 → 失败原因： 跨块关键词无法匹配 → 修正方法： 在块之间传递自动机状态。
追问及应对
为什么不对每个关键词使用 KMP？
分别运行 KMP 需要 O(KN) 扫描；Aho–Corasick 在共享 Trie 前缀后一次处理文本，更适合关键词集合固定且文本很长的场景。
失败链接如何保证不会漏匹配？
它指向当前字符串的最长可用后缀；沿失败链继续走会枚举所有也是关键词前缀的后缀，因此输出聚合能发现嵌套和重叠匹配。
内存被子节点哈希表耗尽怎么办？
按字符集选择数组、紧凑边表或双数组 Trie，并考虑输出链接避免复制列表；先测量节点数和边数再决定压缩策略。
关键词经常变化还能用吗？
把词典版本化，在后台构建新自动机，完成校验后原子替换读指针；短窗口内保留旧版本处理正在进行的流。