一、如何实现敏感词过滤：

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

<1>、单模式串匹配算法：

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

<2>、基于单模式串实现敏感词过滤的方法：

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

2、基于Trie树实现的敏感词过滤：

<1>、多模式串匹配算法：

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

<2>、基于Trie树实现敏感词过滤的方法：

  对敏感词字典进行预处理，构建成Trie树结构。这个预处理的操作只需要做一次，如果敏感词字典动态更新了，比如删除、添加了一个敏感词，只需要动态更新一下Trie树即可。当用户输入一个文本内容后，把用户输入的内容作为主串，从第一个字符（假设是字符C）开始，在Trie树中匹配。当匹配到Trie树的叶子节点，或者中途遇到不匹配字符的时候，将主串的开始匹配位置后移一位，也就是从字符C的下一个字符开始，重新在Trie树中匹配。

二、AC自动机：

1、AC自动机概念：

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

2、AC自动机的代码表示：

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

3、AC自动机的构建操作：

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

4、AC自动机构建失败指针的方法：

<1>、构建思路：

假设这里有4个模式串，分别是c， bc， bcd， abcd；主串是abcd。

<2>、构建代码：

public void buildFailurePointer() {
    Queue<AcNode> queue = new LinkedList<>();
    root.fail = null;
    queue.add(root);
    while (!queue.isEmpty()) {
        AcNode p = queue.remove();
        for (int i = 0; i < 26; ++i) {
            AcNode pc = p.children[i];
            if (pc == null) continue;
            if (p == root) {
                pc.fail = root;
            } else {
                AcNode q = p.fail;
                while (q != null) {
                    AcNode qc = q.children[pc.data - 'a'];
                    if (qc != null) {
                        pc.fail = qc;
                        break;
                    }
                    q = q.fail;
                }
                if (q == null) {
                    pc.fail = root;
                }
            }
            queue.add(pc);
        }
    }
}

5、在AC自动机上匹配主串的方法：

<1>、原理：

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

• 如果p指向的节点有一个等于b[i]的子节点x，就更新p指向x，这个时候需要通过失败指针，检测一系列失败指针为结尾的路径是否是模式串。处理完之后，将i加一，继续这两个过程；
• 如果p指向的节点没有等于b[i]的子节点，让p=p->fail，然后继续这两个过程。

<2>、代码：

public void match(char[] text) { // text是主串
    int n = text.length;
    AcNode p = root;
    for (int i = 0; i < n; ++i) {
        int idx = text[i] - 'a';
        while (p.children[idx] == null && p != root) {
            p = p.fail; // 失败指针发挥作用的地方
        }
        p = p.children[idx];
        if (p == null) p = root; // 如果没有匹配的，从root开始重新匹配
        AcNode tmp = p;
        while (tmp != root) { // 打印出可以匹配的模式串
            if (tmp.isEndingChar == true) {
                int pos = i-tmp.length+1;
                System.out.println("匹配起始下标" + pos + "; 长度" + tmp.length);
            }
            tmp = tmp.fail;
        }
    }
}