AC自动机

AC自动机

AC自动机，全称是Aho-Corasick算法。

AC自动机，实际上就是Trie树的改进。

单模式串、双模式串匹配算法

• 单模式串匹配算法：

  在一个模式串和一个主串之间进行匹配。如BF算法、RK算法、BM算法、KMP算法。

  需要扫描多次主串，比较次数过多，效率低下。

• 双模式串匹配算法：

  在多个模式串和一个主串之间匹配，即在一个主串中查找多个模式串。如Trie树、AC自动机。

  只需要扫描一次主串，就能在主串中一次性查找多个模式串是否存在，效率较高。

Trie树实现的敏感词过滤

• 对敏感词进行预处理，构建出Trie树结构。

• 用户输入文本内容，从第一个字符开始（记为C），在Trie树中匹配。

• 当匹配到Trie的叶子节点，或者中途遇到不匹配字符时，就将主串的开始匹配位置后移一位，即从C+1开始重新匹配。

AC自动机实现的敏感词过滤

• AC自动机的构建：

  • 将多个模式串构建成Trie树。

  • 在Trie树上构建失败指针。

• 构建失败指针：

  • 假设沿Trie树走到P节点，对于从root到节点P形成的字符串，找到最长的可匹配后缀子串。

  • 所谓可匹配后缀子串，就是该子串可匹配某个模式串的前缀。

  • 将节点P的失败指针，指向那个最长可匹配后缀子串对应模式串前缀的最后一个节点。

  • 某个节点的失败指针，只有可能出现在它所在层的上一层。

  • 首先将root的失败指针指向null，然后根据上一个节点的失败指针，查找子节点的失败指针。

  • 具体查找逻辑和KMP算法逻辑类似。假设p节点的失败指针指向q节点，如果p节点的子节点pc对应字符在节点q的子节点qc中找到，将pc的失败指针指向节点qc。如果qc不存在，则在q的失败指针指向节点中继续寻找。如果最后找不到相同字符节点，则让pc指向root。

• AC自动机上匹配主串：

  主串为a，从i=0开始，AC自动机从p=root开始。循环执行一下操作，直到主串匹配结束。

  • 如果p指向节点中存在等于a[i]的子节点，就将p指向该子节点，并且检测以该节点结尾的路径中是否存在模式串。处理完后i加一。

  • 如果p指向节点中不存在等于a[i]的子节点，就让p等于它的失败指针。循环执行这一检查操作，直到p指向root，或者找到子节点。

  • 不停地循环执行以上两个操作。

• 性能分析：

  构建失败指针地时间复杂度为O(k*len)。

  匹配主串的时间复杂度为O(n*len)，因为敏感词并不会很长，所以时间复杂度近似于O(n)。