如何用字典树实现敏感词过滤？AC 自动机又是什么？

简化版

把所有敏感词建成一棵 Trie，然后扫描文本：从每个位置尝试沿 Trie 匹配，匹配到 isEnd 就命中一个敏感词。但朴素 Trie 匹配失败要回退重来。AC 自动机（Aho-Corasick） 是 Trie 的升级——给每个节点加一个 fail 指针（失败指针），匹配失败时不用回退到文本头，而是顺着 fail 指针跳到「最长可复用的后缀」继续，从而一次扫描 O(n+m) 就能找出文本里所有敏感词。

详细版

朴素 Trie 过滤：

把敏感词全部插入一棵 Trie。
遍历文本，以每个字符为起点，沿 Trie 往下匹配。
匹配到 isEnd 节点 → 命中敏感词（可替换成 ***）。
匹配断了 → 换下一个起点重来。

问题：每个起点都可能重新匹配一遍，最坏 O(n × 敏感词长)，且不同起点重复劳动。

AC 自动机 = Trie + fail 指针：

Trie：存所有模式串（敏感词）。
fail 指针：每个节点指向「以当前节点代表的字符串的最长真后缀为前缀的那个 Trie 节点」。匹配失败时沿 fail 指针跳转，复用已匹配的部分，不回退文本指针。
匹配：文本指针只往前走一遍，配合 fail 指针，一次扫描找出所有出现的模式串。O(n + 所有匹配)。

完整版教学

一、为什么敏感词过滤适合用 Trie

敏感词过滤是多模式串匹配：有一大批敏感词，要在文本里找出所有出现的。如果对每个敏感词单独跑一次字符串匹配（如 KMP），有 k 个词就要扫 k 遍文本。Trie 的价值是把所有敏感词合并成一棵树，公共前缀共享，然后一次遍历文本就能同时尝试匹配所有词——因为沿 Trie 下降时，一条路径可能同时是多个敏感词的前缀。

二、朴素 Trie 匹配的瓶颈

朴素做法从文本每个位置起，沿 Trie 尽量匹配。它的问题是匹配失败后要”回退”：比如文本是 she，敏感词有 he，当从 s 起匹配 sh... 失败后，得退回从 h 重新起匹配 he。这个「失败就换起点重来」浪费了已经匹配的信息（h 其实已经看过了）。AC 自动机就是来消除这种回退的。

三、fail 指针：AC 自动机的灵魂

fail 指针让匹配失败时「聪明地跳转」而不是「回退重来」。一个节点的 fail 指针指向：在整棵 Trie 中，以「当前节点对应字符串的最长真后缀」为路径的那个节点。

直观理解：当你沿 Trie 匹配 shar 到某处失败了，fail 指针会带你跳到「har / ar / r 中最长的、还在 Trie 里有对应前缀路径」的位置，继续匹配，而文本指针一步都不用退。这就像 KMP 的 next 数组，只不过 AC 自动机是「多模式串版的 KMP」。

fail 指针通过对 Trie 做一遍 BFS 构建（根的孩子 fail 指向根，其余节点的 fail 由父节点的 fail 推导）。

四、AC 自动机的完整流程

建 Trie：插入所有敏感词。
构建 fail 指针：BFS 遍历 Trie，为每个节点计算 fail。
匹配：文本指针从左到右扫一遍，当前节点没有对应子节点就沿 fail 跳转；每到一个节点，顺着它的 fail 链检查有没有 isEnd（可能同时匹配多个以此结尾的词）。

复杂度 O(n + m + z)：n 是文本长、m 是所有模式串总长（建自动机）、z 是匹配总数。文本只扫一遍，这是它碾压朴素做法的地方。

五、工程中的敏感词过滤

数据量小 / 敏感词少：朴素 Trie 匹配就够，简单。
文本量大 / 敏感词多（如 IM、评论审核）：用 AC 自动机，一次扫描搞定所有词，性能稳定。
实际系统还要处理：变形绕过（傻@逼、拼音、繁简、全半角）、大小写归一化、白名单等，但底层匹配引擎通常就是 Trie / AC 自动机。

六、常见误区与追问

考点	正确口径
朴素 Trie	每个起点都尝试向后匹配
AC 自动机	Trie + fail 指针复用失败后的最长后缀
工程处理	命中后替换、标记或审核

build trie
build fail links by BFS
scan text:
  while no edge: state = fail[state]
  state = next state
  check outputs

AC 自动机的价值在于失败时不回到文本下一起点，而是沿 fail 指针复用已匹配后缀。

误区：敏感词过滤只能逐个词匹配。 多模式匹配可以把词库建成 Trie，再用 AC 自动机一次扫描文本。
误区：fail 指针是回到根节点。 fail 指向当前字符串的最长可匹配后缀节点，只有找不到合适后缀时才回根。
误区：命中一个词后一定立刻停止。 可能存在重叠词、包含词和最长匹配策略，需要按业务规则处理。
追问：朴素 Trie 的瓶颈是什么？ 每个文本位置都可能重新开始匹配，最坏会有大量重复比较。
追问：AC 自动机预处理成本是什么？ 构建 Trie 和 fail 指针，通常与词库总字符数和字符集规模相关。
追问：工程中过滤要注意什么？ 要处理大小写、全半角、变体字符、误杀和白名单等问题，算法只是基础。

七、加强记忆

敏感词过滤是多模式串匹配：把敏感词建成 Trie，一次遍历文本同时匹配所有词。朴素 Trie 匹配失败要回退换起点、有重复劳动。AC 自动机 = Trie + fail 指针（多模式串版 KMP）：fail 指针指向「最长真后缀对应的节点」，匹配失败时沿 fail 跳转、文本指针不回退，一次扫描 O(n+m+z) 找出所有敏感词。词多量大用 AC 自动机。

简化版

详细版