36.AC自动机：如何用多模式串匹配实现敏感词过滤功能

多模式串匹配算法: 那如何才能实现一个高性能的敏感词过滤系统呢？

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

• 单模式串匹配算法: BF算法、RK算法、BM算法、KMP算法
• 多模式串匹配算法: Trie树

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

2.1 AC节点代码表示

AC自动机实际上就是在Trie树之上，加了类似KMP的next数组，只不过此处的next数组是构建在树上罢了。

代码表示：

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

2.2 如何构建失败指针

• 最长可匹配后缀子串和可匹配后缀子串
  
• 已经求得某个节点p的失败指针之后，如何寻找它的子节点的失败指针呢？

root的fail指针为NULL，即它自己。

• 代码

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

• 刚才例子的计算结果
  

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

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