BBS等文本内容网站，大都会有敏感词过滤功能，用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。
实际上，这些功能最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容之后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“***”把它替代掉。
单模式字符串匹配算法都可以处理这个问题。但是，对于访问量巨大的网站来说，比如淘宝，用户每天的评论数有几亿、甚至几十亿。这时候，对敏感词过滤系统的性能要求就要很高。毕竟，我们也不想，用户输入内容之后，要等几秒才能发送出去吧？我们也不想，为了这个功能耗费过多的机器吧？
如何实现一个高性能的敏感词过滤系统，即多模式串匹配算法。
1. 基于单模式串和Trie树实现的敏感词过滤
字符串匹配算法，有 BF 算法、RK 算法、BM 算法、KMP 算法（单模式串匹配算法），还有 Trie 树（多模式串匹配算法）。
单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串 中查找一个模式串。
多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说， 在一个主串中查找多个模式串。
尽管，单模式串匹配算法也能完成多模式串的匹配工作。可以针对每个敏感词，通过单模式串匹配算法（比如 KMP 算法）与用户输入的文字内容进行匹配。但这样做，每个匹配过程都需要扫描一遍用户输入的内容。整个过程下来就要扫描很多遍用户输入的内容。如果敏感词很多，比如几千个，并且用户输入的内容很长，假如有上千个字符，那就需要扫描几千遍这样的输入内容。很显然，这种处理思路比较低效。
与单模式匹配算法相比，多模式匹配算法在这个问题的处理上就很高效了。它只需要扫描一遍主 串，就能在主串中一次性查找多个模式串是否存在，从而大大提高匹配效率。Trie 树就是一种多模式串匹配算法。
那如何用 Trie 树实现敏感词过滤功能呢？
对敏感词字典进行预处理，构建成 Trie 树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，只需要动态更新一下 Trie 树 就可以了。
当用户输入一个文本内容后，我们把用户输入的内容作为主串，从第一个字符（假设是字符 C） 开始，在 Trie 树中匹配。当匹配到 Trie 树的叶子节点，或者中途遇到不匹配字符的时候，我们 将主串的开始匹配位置后移一位，也就是从字符 C 的下一个字符开始，重新在 Trie 树中匹配。
基于 Trie 树的这种处理方法，有点类似单模式串匹配的 BF 算法。单模式串匹配算法中，KMP 算法对 BF 算法进行改进，引入了 next 数组，让匹配失败时，尽可能将模式串往后 多滑动几位。借鉴单模式串的优化改进方法，能否对多模式串 Trie 树进行改进，进一步提高 Trie 树的效率呢？这就要用到 AC 自动机算法了。
2. 经典的多模式串匹配算法：AC 自动机
AC 自动机算法，全称 Aho-Corasick 算法。其实，Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。
AC 自动机的构建，包含两个操作：
- 将多个模式串构建成 Trie 树；
- 在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。
构建好 Trie 树之后，如何在它之上构建失败指针？
比如：4 个模式串，分别是 c，bc，bcd，abcd；主串是 abcd。
Trie 树中的每一个节点都有一个失败指针，它的作用和构建过程，跟 KMP 算法中的 next 数组极其相似。要先理解 KMP 算法中 next 数组的构建过程。
假设沿Trie树走到p节点，即下图中的紫色节点，那p的失败指针就是从root走到紫色节点形成的字符串abc，跟所有模式串前缀匹配的长可匹配后缀子串，就是箭头指的 bc 模式串。
这里的最长可匹配后缀子串: 字符串abc的后缀子串有两个 bc，c，拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，那就把这个后缀子串叫作可匹配后缀子串。
从可匹配后缀子串中，找出长的一个，就是刚刚的最长可匹配后缀子串。将p节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的后一个节点，就是下图中箭头指向的节点。
计算每个节点的失败指针这个过程看起来有些复杂。其实，如果把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。
可以像KMP算法那样，当要求某个节点的失败指针的时，我们通过已经求得的深度更小的那些节点的失败指针来推导。也就是说，我们可以逐层依次来求解每个节点的失败指针。所以，失败指针的构建过程，是一个按层遍历树的过程。
首先 root的失败指针为NULL，也就是指向自己。当我们已经求得某个节点 p 的失败指针之后，如何寻找它的子节点的失败指针呢？
我们假设节点p 的失败指针指向节点q，我们看节点 p 的子节点 pc 对应的字符，是否也可以在节点q 的子节点中找到。如果找到了节点q 的一个子节点 qc，对应的字符跟节点 pc 对应的字符相同，则将节点 pc 的失败指针指向节点 qc。
如果节点q 中没有子节点的字符等于节点 pc 包含的字符，则令 q=q->fail（fail 表示失败指 针，这里有没有很像 KMP 算法里求 next 的过程？），继续上面的查找，直到 q 是 root 为 止，如果还没有找到相同字符的子节点，就让节点 pc 的失败指针指向 root。
按层来计算每个节点的子节点的失效指针，刚刚那个例子，最后构建完成之后的 AC 自动机就是下面这个样子：
AC 自动机构建完成。现在来看下，如何在 AC 自动机上匹配主串？
还是拿之前的例子来讲解。在匹配过程中，主串从 i=0 开始，AC 自动机从指针 p=root 开始，假设模式串是 b，主串是 a。
- 如果 p 指向的节点有一个等于 b[i] 的子节点 x，我们就更新 p 指向 x，这个时候我们需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。这一句不好理解，你可以结合代码看。处理完之后，我们将 i 加一，继续这两个过程；
- 如果 p 指向的节点没有等于 b[i] 的子节点，那失败指针就派上用场了，我们让 p=p->fail，然后继续这 2 个过程。
AC 自动机实现的敏感词过滤系统，是否比单模式串匹配方法更高效呢？
首先，我们需要将敏感词构建成 AC 自动机，包括构建 Trie 树以及构建失败指针。我们上一节讲过，Trie 树构建的时间复杂度是 O(m*len)，其中 len 表示敏感词的平均长度，m
表示敏感词的个数。那构建失败指针的时间复杂度是多少呢？我这里给出一个不是很紧确的上界。假设 Trie 树中总的节点个数是 k，每个节点构建失败指针的时候，（你可以看下代码）最耗时的环节是 while 循环中的 q=q->fail，每运行一次这个语句，q 指向节点的深度都会减少 1，而树的高度最高也不会超过 len，所以每个节点构建失败指针的时间复杂度是 O(len)。整个失败指针的构建过程就是 O(k*len)。不过，AC 自动机的构建过程都是预先处理好的，构建好之后，并不会频繁地更新，所以不会影响到敏感词过滤的运行效率。
再来看下，用 AC 自动机做匹配的时间复杂度是多少？
跟刚刚构建失败指针的分析类似，for 循环依次遍历主串中的每个字符，for 循环内部最耗时的部分也是 while 循环，而这一部分的时间复杂度也是 O(len)，所以总的匹配的时间复杂度就是O(n*len)。因为敏感词并不会很长，而且这个时间复杂度只是一个非常宽泛的上限，实际情况下，可能近似于 O(n)，所以 AC 自动机做敏感词过滤，性能非常高。
你可以会说，从时间复杂度上看，AC 自动机匹配的效率跟 Trie 树一样啊。实际上，因为失效指针可能大部分情况下都指向 root 节点，所以绝大部分情况下，在 AC 自动机上做匹配的效率要远高于刚刚计算出的比较宽泛的时间复杂度。只有在极端情况下，如图所示，AC 自动机的性能才会退化的跟 Trie 树一样。
小结
多模式串匹配算法，AC 自动机。单模式串匹配算法是为了快速在主串中查找一个模式串，而多模式串匹配算法是为了快速在主串中查找多个模式串。
AC 自动机是基于 Trie 树的一种改进算法，它跟 Trie 树的关系，就像单模式串中，KMP 算法与BF 算法的关系一样。KMP 算法中有一个非常关键的 next 数组，类比到 AC 自动机中就是失败指针。而且，AC 自动机失败指针的构建过程，跟 KMP 算法中计算 next 数组极其相似。所以，要理解 AC 自动机，最好先掌握 KMP 算法，因为 AC 自动机其实就是 KMP 算法在多模式串上的改造。
整个 AC 自动机算法包含两个部分，第一部分是将多个模式串构建成 AC 自动机，第二部分是在AC 自动机中匹配主串。第一部分又分为两个小的步骤，一个是将模式串构建成 Trie 树，另一个是在 Trie 树上构建失败指针。
一、单模式串匹配：
1. BF： 简单场景，主串和模式串都不太长, O(m*n)
2. KP： 字符集范围不要太大且模式串不要太长， 否则hash值可能冲突，O(n)
3. naive-BM：模式串最好不要太长（因为预处理较重），比如IDE编辑器里的查找场景； 预处理O(m*m), 匹配O(n)， 实现较复杂，需要较多额外空间.
4. KMP：适合所有场景，整体实现起来也比BM简单，O(n+m)，仅需一个next数组的O(n)额外空间；但统计意义下似乎BM更快，
5. 另外查资料的时候还看到一种比BM/KMP更快，且实现+理解起来都更容易的的Sunday算
法，有兴趣的可以看这里:
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
https://www.jianshu.com/p/2e6eb7386cd3
二、多模式串匹配：
1. naive-Trie: 适合多模式串公共前缀较多的匹配(O(n*k)) 或者 根据公共前缀进行查找(O(k))
的场景，比如搜索框的自动补全提示.
2. AC自动机: 适合大量文本中多模式串的精确匹配查找, 可以到O(n).