BBS等文本内容网站，大都会有敏感词过滤功能，用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。

实际上，这些功能最基本的原理就是字符串匹配算法，也就是通过维护一个敏感词的字典，当用户输入一段文字内容之后，通过字符串匹配算法，来查找用户输入的这段文字，是否包含敏感词。如果有，就用“***”把它替代掉。

单模式字符串匹配算法都可以处理这个问题。但是，对于访问量巨大的网站来说，比如淘宝，用户每天的评论数有几亿、甚至几十亿。这时候，对敏感词过滤系统的性能要求就要很高。

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

常见的字符串匹配算法，有 BF 算法、RK 算法、BM 算法、KMP 算法，还有 Trie 树。前面四种算法都是单模式串匹配算法，只有 Trie 树是多模式串匹配算法。

单模式串匹配算法，是在一个模式串和一个主串之间进行匹配，也就是说，在一个主串中查找一个模式串。

多模式串匹配算法，就是在多个模式串和一个主串之间做匹配，也就是说，在一个主串中查找多个模式串。

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

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

AC自动机比Trie树牛在哪里，其实就是添加了fail指针可以减少匹配次数。

AC 自动机算法，全称是 Aho-Corasick 算法。Trie 树跟 AC 自动机之间的关系，就像单串匹配中朴素的串匹配算法，跟 KMP 算法之间的关系一样，只不过前者针对的是多模式串而已。所以，AC 自动机实际上就是在 Trie 树之上，加了类似 KMP 的 next 数组，只不过此处的 next 数组是构建在树上罢了。

如果代码表示，就是下面这个样子：

public class AcNode {public char data; public AcNode[] children = new AcNode[26]; // 字符集只包含 a~z 这 26 个字符public boolean isEndingChar = false; // 结尾字符为 truepublic int length = -1; // 当 isEndingChar=true 时，记录模式串长度public AcNode fail; // 失败指针public AcNode(char data) {this.data = data;}
}

所以，AC 自动机的构建，包含两个操作：

• 将多个模式串构建成 Trie 树；
• 在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）。

3、经典AC自动机代码实现

LeetCode1032是一道典型的多模式匹配题目。

class StreamChecker {TrieNode root;TrieNode temp;public StreamChecker(String[] words) {root = new TrieNode();for (String word : words) {TrieNode cur = root;for (int i = 0; i < word.length(); i++) {int index = word.charAt(i) - 'a';if (cur.getChild(index) == null) {cur.setChild(index, new TrieNode());}cur = cur.getChild(index);}cur.setIsEnd(true);}root.setFail(root);Queue<TrieNode> q = new LinkedList<>();for (int i = 0; i < 26; i++) {if (root.getChild(i) != null) {root.getChild(i).setFail(root);q.add(root.getChild(i));} else {root.setChild(i, root);}}while (!q.isEmpty()) {TrieNode node = q.poll();node.setIsEnd(node.getIsEnd() || node.getFail().getIsEnd());for (int i = 0; i < 26; i++) {if (node.getChild(i) != null) {node.getChild(i).setFail(node.getFail().getChild(i));q.offer(node.getChild(i));} else {node.setChild(i, node.getFail().getChild(i));}}}temp = root;}public boolean query(char letter) {temp = temp.getChild(letter - 'a');return temp.getIsEnd();}
}
class TrieNode {TrieNode[] children;boolean isEnd;//添加失败指针TrieNode fail;public TrieNode() {children = new TrieNode[26];}public TrieNode getChild(int index) {return children[index];}public void setChild(int index, TrieNode node) {children[index] = node;}public boolean getIsEnd() {return isEnd;}public void setIsEnd(boolean b) {isEnd = b;}public TrieNode getFail() {return fail;}public void setFail(TrieNode node) {fail = node;}
}