用多模式串匹配实现敏感词过滤

基于单模式串和 Trie 树实现的敏感词过滤

BF 算法、RK 算法、BM 算法、KMP 算法，还有 Trie 树这几种算法中，只有Trie树是多模式串匹配算法。

单模式串匹配中，匹配每个模式串时都需要遍历一遍主串，相比之下，多模式串匹配只需要遍历一遍主串，所以后者效率会更高。

如何用 Trie 树实现敏感词过滤功能

我们可以对敏感词字典进行预处理，构建成 Trie 树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，那我们只需要动态更新一下 Trie 树就可以了。

当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符 C）开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。

基于 Trie 树的这种处理方法，有点类似单模式串匹配的 BF 算法。所以可以进一步改进–>AC 自动机

经典的多模式串匹配算法：AC 自动机

构建AC自动机

类似KMP算法的next失效数组构建方式，这里叫做失效指针

我们可以逐层依次来求解每个节点的失败指针。

构建好的样子如下图：

如何在 AC 自动机上匹配主串？

在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。

• 如果 p 指向的节点有一个等于 b[i]的子节点 x，我们就更新 p 指向 x，这个时候我们需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。这一句不好理解，你可以结合代码看。处理完之后，我们将 i 加一，继续这两个过程；
• 如果 p 指向的节点没有等于 b[i]的子节点，那失败指针就派上用场了，我们让 p=p->fail，然后继续这 2 个过程。