# 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)`。
