从KMP到AC自动机

### 0 什么是自动机 我到现在也不知道什么是自动机。 你们也没必要深刻理解这个问题。 ### 1 要学什么自动机 AC自动机、回文自动机（PAM，回文树）、后缀自动机（SAM）。 事实上，OI中最实用的字符串算法只有：Hash、PAM、SAM。KMP可以现场脑补出来，manacher可以用Hash替代（多一个$\log$），AC自动机基本可以用SA（后缀数组）替代，SAM可以建出SA，PAM可以秒杀各种SAM+manacher的神题。 在各种膜你赛中，我只用过Hash和SA。 ### 2 什么是AC自动机 一种多模式串的字符串匹配算法。不能用于自动AC。 ### 3 AC自动机的原理 AC自动机就是Trie树上的KMP。 | KMP | AC Automaton | | :----------- | :----------- | | 字符串 | Trie | | 失配数组```next[]``` | 失配数组```fail[]``` | 回忆一下KMP: 我们一位一位匹配模式串与文本串。在失配时，我们借助预先求出的next数组在模式串上向前跳转。 其实，单个模式串可以看做是一个单链形的Trie树。所以在AC自动机中： 我们在模式串构成的Trie树上顺着给出的文本串走路。当我们发现没有相应的子节点时，类似于KMP，我们借助预先求出的fail数组在Trie树上向前跳转。 ### 4 如何借助（朴素方法构造的）fail跳转 假如我们已经构造了下图的AC自动机，途中的黑边为Trie树，红边和绿边为fail数组。  可以发现AC自动机的```fail```和KMP的```next```就是一个东西。对于```v=fail[u]```来说，在```u```的所有后缀中，```v```是Trie树中存在的最长前缀。 我们类比KMP进行跳转。 ``` int query(char T[]) { int res=0,pos=0; for(int i=0;T[i];++i) { int trans=T[i]-'a'; while(!trie[pos].next[trans]&&pos) { pos=trie[pos].fail; } pos=trie[pos].next[trans]; int temp=pos; while(temp&&trie[temp].tail!=-1) { res+=trie[temp].tail; trie[temp].tail=-1; temp=trie[temp].fail; } } return res; } ``` ### 4 AC自动机的构造 先建Trie树，正常建就行。关键在于如何在线性时间内构造fail数组。构造AC自动机的过程是一个对Trie树进行BFS的过程。 和KMP差不多，我们不难想到： #### 朴素的构造方法 设这个节点上的字母为c，沿着他父亲的fail走，直到走到一个节点，他的儿子中也有字母为c的节点，我们就找到了所求的fail。 ``` void Get_Fail() { std::queue<int>Q; Q.push(0); while(!Q.empty()) { int temp=Q.front(); Q.pop(); for(int i=0;i<26;++i) { if(trie[temp].next[i]) { int prev=trie[temp].fail; while(prev) { if(trie[prev].next[i]) { trie[trie[temp].next[i]].fail=trie[prev].next[i]; break; } else { prev=trie[prev].fail; } } Q.push(trie[temp].next[i]); } } } } ``` 这个方法的弊端很明显，往前跳fail的时候可能要跳很远才能找到匹配。 #### 从字典树到字典图 还有一种加特技的写法。 ``` void Get_Fail() { queue<int>qu; for(int i=0;i<26;++i)//迷思1 { if(trie[0].next[i]) { trie[trie[0].next[i]].fail=0; qu.push(trie[0].next[i]); } } int fa; while(!qu.empty()) { fa=qu.front(); qu.pop(); for(int i=0;i<26;++i) { if(trie[fa].next[i]) { trie[trie[fa].next[i]].fail=trie[trie[fa].fail].next[i];//迷思2 qu.push(trie[fa].next[i]); } else trie[fa].next[i]=trie[trie[fa].fail].next[i];//迷思3 } } } ``` 迷思1：为什么要先让根节点的所有儿子入队？只让根节点入队不行吗？ 真的不行。我们模拟一遍试试（暂时认为while里面的代码是完全正确的）。 如果直接让根节点入队，考虑根节点的所有儿子： ``` for(c in 字符集) { if(存在这个子节点c) { 这个子节点的fail=根节点的这个子节点 } else { 根节点的这个子节点=根节点的这个子节点 } } ``` 自己的fail怎么指向自己了？显然不对。根据定义，每个子节点的fail明明一定指向根节点。 于是我们强行钦点他们的fail为根节点，也就是0。我们发现，这样构造出的AC自动机是正确的。 迷思2：为什么直接把fail指针的next赋给子节点的fail？你怎么就知道fail一定有这个儿子呢？ 迷思3：怎么直接把trie树的结构改了？随随便便就加儿子？ 这其实是一种路径压缩。为了达到路径压缩的目的，我们首先要将所有节点的26个子节点补齐。我们已经发现，在这种加特技的方法里，子节点是可以往回连的。因此这个东西已经不满足树的定义，不能被称为trie树了。我们称它为trie图。 （在黑板上画一下） 要是仍然不理解，先把代码背下来，以后就会明白的。 这种构造方法还有一个好处，那就是查询函数也可以化简。 ``` int Query() { int res=0,pos=0; for(int i=0;i<length;++i) { pos=trie[pos].next[s[i]-'a']; for(int j=pos;j&&trie[j].tail!=-1;j=trie[j].fail) { res+=trie[j].tail; trie[j].tail=-1; } } printf("%d",res); } ```