BF 算法、RK 算法、BM 算法、KMP 算法，都是单模式串匹配算法。Trie 树是多模式串匹配算法。

• 单模式串匹配算法，就是在一个主串中查找一个模式串。
• 多模式串匹配算法，就是在一个主串中查找多个模式串。

AC 自动机（Aho-Corasick）算法，是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像单模式串中，KMP 算法与 BF 算法的关系一样。

如何实现敏感词过滤功能 #

可以针对每个敏感词，通过单模式串匹配算法（比如 KMP 算法）与用户输入的文字内容进行匹配。但是，这样每个匹配过程都需要扫描一遍用户输入的内容。 整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多，比如几千个，并且用户输入的内容很长，假如有上千个字符，那就需要扫描几千遍这样的 输入内容。很显然，这种处理思路比较低效。

多模式匹配算法要更高效。如何用 Trie 树实现敏感词过滤功能？

把敏感词字典构建成 Trie 树结构。用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点， 或者中途遇到不匹配字符的时候，将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。 这种处理方法，有点类似单模式串匹配的 BF 算法。可以借鉴 KMP 算法对多模式串 Trie 树进行改进。这就需要 AC 自动机算法。

AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上。