AC自动机学习笔记

前言 & 介绍

学习AC自动机时，发现很多讲解都比较难以理解（可能是我太菜了）。
通过学习dalao的学习笔记，自主研发和学长的讲解终于贯彻理解了AC自动机（真的贯彻吗）。
所以，我尝试发一篇我认为比较容易理解的讲解。
前置知识：

• 字典树（trie树）
  
• KMP（非必会）
  

介绍：

AC自动机是一种可以解决多匹配串和单文本串的字符串匹配算法，是一种有限状态自动机，如果你学过KMP，那么理解起来相对轻松，它的理解难度低于KMP算法。
正文：

有限状态自动机：

有限状态自动机是为研究有限内存的计算过程和某些语言类而抽象出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。
——摘自百度百科

怎么样，理解没？我猜你没理解，那我们用人类语言描述一下吧。
如果你上过初中，那你肯定做过模拟程序运行题，给你一个程序流程图，让你预测它的输出结果，它就是一种简单的自动机模型。
本质上，自动机就是输入一种信号，在它内部经过决策和计算，最终接受答案的数学模型，我们要做到就是实现它内部的决策与计算。
AC自动机：

首先用一道例题引入 :
给定 \(n\) 个模式串 \(s_i\) 和一个文本串 \(t\)，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们编号不同。

• 对于 \(50\%\) 的数据，保证 \(n = 1\)。
  
• 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^6\)，\(1 \leq |t| \leq 10^6\)，\(1 \leq \sum\limits_{i = 1}^n |s_i| \leq 10^6\)。\(s_i, t\) 中仅包含小写字母。
  

如果我们直接上KMP，对于每个匹配串都求一个next，时间和空间都是爆炸的，这时候，我们就引入了AC自动机。
我们考虑KMP之所以不能在优秀的时间复杂度内求出，瓶颈在于多次求next，有什么办法优化呢？
我们考虑用匹配串建一棵trie树，通过维护一个指针来在这棵树上计算答案。
具体来说，我们维护一个fail指针，使我们在计算答案时可以通过跳指针来统计所有以当前节点字符结尾
的匹配串的答案，并在当前节点的子节点无法匹配时跳到可以匹配的节点继续匹配。
那么我们考虑怎么建这个fail指针。
直接说定义，fail指针指向与当前节点结尾的后缀匹配的树上最长前缀的结尾节点。
是不是和KMP的next很像？当然不会KMP也可以理解。
考虑为什么这样可以不重不漏统计所有答案。我们发现，如果当前节点所代表的匹配串与文本串匹配，那么根据fail指针定义，这个节点的fail指针指向的节点到根节点的链一定可以与文本串匹配，这是显然的，那么我们如果一直跳指针，在这个节点是结尾节点时累计答案即可。
对于fail指针的第二个作用，我们考虑如果当前节点的子节点没有能与文本串当前位置匹配的字符，我们通过跳fail指针，可以继续寻找与文本串下一个字符匹配，且前缀与文本串匹配的节点。
特别的，对于没有合法节点可以连接的节点，它的fail指针指向虚根 \(0\)。
显然，这一过程可以BFS实现，如果通过找到当前节点的父节点的fail指针指向的节点，我们将当前节点的fail指针指向这个节点的与当前节点字符相同的子节点即可，形式化的，即：

\[fail[son]=son[fail]\]
匹配与建树过程是平凡的，与trie树流程大体相同，这里不做赘述。
代码 ：

[code]#include#define Robin 0using namespace std;const int N=1e6+10;string s;string t;int n;struct Tree{        int son[26];        int fail;        int end;} Ac[N];int cnt,ans;inline void insertTree(string a){        int len=a.size();        int now=0;        for(int i=0;i