AC自动机

基于单模式串和Trie树实现

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

Trie树是一种多模式串匹配算法。
对敏感词字典进行预处理，构建成Trie树结构。预处理操作只需要做一次，敏感词字典动态更新（删除、添加），只需要动态更新一下Trie树。

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

类似单模式串匹配的BF算法。

多模式串匹配算法

基本原理

AC自动机算法（Aho-Corasick算法）。
Trie树跟AC自动机之间的关系，类似于单串匹配中朴素的串匹配算法跟KMP算法之间的关系。
AC自动机实际上就是再Trie树之上，加了类似KMP的next数组，只不过此处的next数组时构建在树上罢了。

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;//失败指针
    punlic AcNode(char data) {
        this.data = data;
    }
}

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

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

Trie树中的每一个节点都有一个失败指针，它的作用和构建过程，跟KMP算法中的next数组极其相似。

沿Trie树走到p节点，p的失败指针就是从root走到p节点形成的字符串abc，跟所有模式串前缀匹配的最长可匹配后缀子串。

字符串abc的后缀子串有两个bc、c，拿它们与其他模式串匹配，如果某个后缀子串可以匹配某个模式串的前缀，就把这个后缀子串叫做可匹配后缀子串。

从匹配后缀子串中，找出最长的一个。将p节点的失败指针指向那个最长匹配后缀子串对应的模式串的前缀的最后一个节点。

把树中相同深度的节点放到同一层，那么某个节点的失败指针只有可能出现在它所在层的上一层。

当要求某个节点的失败指针的时候，通过已经求得的、深度更小的那些节点的失败指针来推导。也就是说可以逐层依次来求解每个节点的失败指针。失败指针的构建过程，是一个按层遍历树的过程。

失败指针

root的失败指针为NULL，就是指向自己。

假设节点p的失败指针指向节点q，看节点p的子节点pc对应的字符，是否也可以在节点q的子节点中找到。如果找到了节点q的一个子节点qc，对应的字符跟节点pc对应的字符相同，则将节点pc的失败指针指向节点qc。

如果节点q中没有子节点的字符等于节点pc包含的字符，则令q=q->fail(fail表示失败指针)，继续上面的查找，直到q是root为止，如果还没有找到相同字符的子节点，就让节点pc的失败指针指向root。

失败指针

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);
        }
    }
}

按层计算每个节点的子节点的失效指针。

匹配主串

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

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

匹配主串

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;
        } 
    }
}

效率分析

构建

将敏感词构建成AC自动机，包括构建Trie树以及构建失败指针。

Trie树构建的时间复杂度是O(m*len)，其中len表示敏感词的平均长度，m表示敏感词的个数。

假设Trie树中总的节点个数是k，每个节点构建失败指针的时候，最耗时的环节是while循环中的q=q->fail，每次运行一次这个语句，q指向节点的深度都会减少1，而树的高度最高也不会超过len，所以每个节点构建失败指针的时间复杂度是O(len)。整个失败指针的构建过程为O(k*len)。

AC自动机的构建过程都是预先处理好的，构建好之后，并不会频繁的更新，不会影响到敏感词过滤的运行效率。

匹配

for循环依次遍历主串中的每个字符，for循环内部最耗时的部分也是while循环，这一部分的时间复杂度是O(len)，总的匹配的时间复杂度就是O(n*len)。敏感词一般不长，实际情况近似于O(n)。

从时间复杂度上看，AC自动机匹配的效率跟Trie树一样。但是失效指针大部分情况下都指向root节点，所以大部分情况下，在AC自动机上做匹配的效率要远高于理论时间复杂度。只有在极端情况边，AC自动机的性能才会退化的根Trie树一样（每个节点的失效指针分别指向自己的父节点）。