强势图解AC自动机
sshwy
2018-08-13 11:20:29
# 前置技能
- [字典树](https://sshwy.gitee.io/2018/10/01/53862/)
- [KMP匹配](https://sshwy.gitee.io/2018/10/01/35921/)
# 简介
看dalao们AC自动机的Blog，大多数奆奆都会感性地说：
`AC_automation = KMP+TRIE`<!--more-->
然而在作者重蹈覆辙辗转反侧n次后才明白，这东西说了等于没说。
- AC自动机是一种**有限状态自动机**（说了等于没说），它常被用于多模式串的字符串匹配。
- 在学完AC自动机，笔者也总结出一句说了等于没说的话：
AC自动机是**以TRIE的结构为基础**，结合**KMP的思想**建立的。
# 建立AC自动机
建立一个AC自动机通常需要两个步骤：
- 基础的TRIE结构：将所有的模式串构成一棵Trie。
- KMP的思想：对Trie树上所有的结点构造失配指针。
然后就可以利用它进行多模式匹配了。
## TRIE构建
- 和trie的insert操作**一模一样**（强调！一模一样！）
- 因为我们只利用TRIE的结构，所以只需将模式串存入即可。
## 构造失配（$fail$）指针
在讲构造以前，先来对比一下这里的$fail$指针与KMP中的next指针：
- 共同点-两者同样是**在失配的时候**用于跳转的指针。
- 不同点-KMP要求的是**最长相同真前后缀**，而AC自动机只需要**相同后缀**即可。
- 因为KMP只对一个模式串做匹配，而AC自动机要对多个模式串做匹配。
- 有可能$fail$指针指向的结点对应着另一个模式串，两者前缀不同。
- 也就是说，AC自动机在对匹配串做逐位匹配时，同一位上可能匹配多个模式串。
- 因此$fail$指针会在字典树上的结点来回穿梭，而不像KMP在线性结构上跳转。
下面介绍构建$fail$指针的**基础思想**：（强调！基础思想！基础！）
- 构建$fail$指针，可以参考KMP中构造next数组的**思想**。
- 我们**利用部分已经求出$fail$指针的结点**推导出当前结点的$fail$指针。具体我们用BFS实现：
- 考虑字典树中当前的节点u，u的父节点是p，p通过字符c的边指向u。
- 假设深度小于u的所有节点的$fail$指针都已求得。那么p的$fail$指针显然也已求得。
- 我们跳转到p的$fail$指针指向的结点$fail[p]$；
- 如果结点$fail[p]$通过字母$c$连接到的子结点$w$存在：
- 则让u的fail指针指向这个结点$w$（$fail[u]=w$）。
- 相当于在$p$和$fail[p]$后面加一个字符$c$，就构成了$fail[u]$。
- 如果$fail[p]$通过字母$c$连接到的子结点$w$不存在：
- 那么我们继续找到$fail[fail[p]]$指针指向的结点，重复上述判断过程，一直跳$fail$指针直到根节点。
- 如果真的没有，就令$fail[u]=$根节点。
- 如此即完成了$fail$指针的构建。
下面放一张GIF帮助大家理解：
对字典树{i,he,his,she,hers}构建$fail$指针：
- 黄色结点表示当前的结点u，绿色结点表示已经BFS遍历完毕的结点，红/橙色的边表示$fail$指针。
- **2号节点的$fail$指针画错了，$fail[2]=0$.**
![AC_automation_gif_b_3.gif][1]
- 我们重点分析结点6的$fail$指针构建：
![AC_automation_6_9.png][2]
- 找到6的父节点5，5的$fail$指针指向10，然而10结点没有字母's'连出的边；
- 所以跳到10的$fail$指针指向的结点0，发现0结点有字母's'连出的边，指向7结点；
- 所以$fail[6]=7$.
另外，在构建$fail$指针的同时，我们也对TRIE中模式串的结尾构建$fail$指针。这样在匹配到结尾后能自动跳转到下一个匹配项。具体见代码实现。
# 从代码深入剖析
## 框架
```cpp
const int N=1000;
struct AC_automaton{
int tr[N][26],cnt;//TRIE
int e[N];//标记这个结点是不是字符串结尾
int fail[N];//fail指针
void insert(char * s){}//插入模式串
void build(){}//构建fail指针
int query(char *t){}//匹配函数
};
AC_automation ac;
}
```
## 字典树与字典图
- 关于`insert()`笔者不做分析，先来看`build()`:
```cpp
void build(){
queue<int>q;
memset(fail,0,sizeof(fail));
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);//Q1
while(!q.empty()){
int k=q.front();q.pop();
for(int i=0;i<26;i++){
if(tr[k][i]){
fail[tr[k][i]]=tr[fail[k]][i];//Q2
q.push(tr[k][i]);
}
else tr[k][i]=tr[fail[k]][i];//Q3
}
}
}
```
首先声明了一个队列用于BFS，并清空$fail$数组。
这里的字典树根节点为0，我们将根节点的子节点一一入队。
- Q1-等等，为什么不将根节点入队，非要将它的子节点入队？
然后开始BFS：
- 每次取出队首的结点k。注意，结点k本身的$fail$指针已经求得，我们要求的是k的子节点们的$fail$指针。
- 然后遍历字符集（这里是0-25，对应a-z）：
- 如果字符i对应的子节点存在，我们就将这个子节点的$fail$指针赋值为$fail[k]$的字符i对应的结点。
- Q2-不是应该用while循环，不停的跳$fail$指针，判断是否存在字符i对应的结点，然后赋值吗？怎么一句话就完了？
- 否则，k结点没有字符i对应的子节点，就将**$fail[k]$的字符i对应的子节点编号赋值给k**
- Q3-等等，说好的字典树呢？怎么将$fail[k]$的子节点直接赋成k的子节点去了？
**这三个Questions构成了$fail$指针构建的精髓。**
### Q1
- 若将根节点入队，则在第一次BFS的时候，会将根节点的子节点的$fail$指针标记为本身。
- 而将根节点的子节点入队，也不影响算法正确性（因为$fail$指针初始化为0）
### Q2&Q3
- Q2与Q3的代码是相辅相成的。
- 简单地来讲，我们将$fail$指针跳转的路径做了压缩（就像并查集的路径压缩），使得本来需要跳很多次$fail$指针变成跳一次。
- 而这个**路径压缩**的就是Q3的代码在做的事情**之一**。
- 我们将之前的GIF图改一下：
![AC_automation_gif_b_pro3.gif][3]
- 蓝色结点表示BFS遍历到的结点k，深蓝色、黑色的边表示执行完Q3代码连出的字典树的边。
- 可以发现，众多交错的黑色边将字典树变成了字典图。
- 图中省略了连向根节点的黑边（否则会更乱）。
- 我们重点分析一下结点5遍历时的情况：
![AC_automation_b_7.png][4]
- 显然，本来应该跳2次才能找到7号结点，但是我们通过10号结点的黑色边直接通过字母s找到了7号结点。
- 因此，Q2结合了Q3的代码，就能在$O(1)$的时间内对单个结点构造$fail$指针。
这就是build完成的两件事：构建$fail$指针和建立字典图。这个字典图也会在查询的时候起到关键作用。
## 多模式匹配
- 接下来分析匹配函数`query()`:
```cpp
int query(char *t){
int p=0,res=0;
for(int i=0;t[i];i++){
p=tr[p][t[i]-'a'];//Q
for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1;
}
return res;
}
```
- 声明p作为字典树上当前匹配到的结点，res即返回的答案
- 循环遍历匹配串，p在字典树上跟踪当前字符。
- 利用$fail$指针找出所有匹配的模式串，累加到答案中。然后清0。
- 对$e[j]$取反的操作用来判断$e[j]$是否等于-1。
- Q-读者可能纳闷了：你这里的p一直在往字典树后面走，没有跳$fail$指针啊！这和KMP的思想不一样啊，怎么匹配得出来啊
### Answer to Q
- 还记得刚才的字典图吗？事实上你并不是一直在往后跳，而是在图上穿梭跳动。比如，刚才的字典图：
![AC_automation_b_13.png][5]
- 我们从根节点开始尝试匹配`ushersheishis`，那么p的变化将是：
![AC_automation_gif_c.gif][6]
- 红色结点表示p结点，粉色箭头表示p在字典图上的跳转，浅蓝色的边表示成功匹配的模式串，深蓝色的结点表示跳$fail$指针时的结点。
- 其中的部分跳转，我们利用的就是新构建的字典图上的边，它也满足后缀相同（sher和her），所以自动跳转到下一个位置。
- 综上，$fail$指针的意义是，在匹配串**同一个位置**失配时的跳转指针，这样就利用$fail$指针在同一位置上进行多模式匹配，匹配完了，就在字典图上自动跳转到下一位置。
## 总结
到此，你已经理解了整个AC自动机的内容。我们一句话总结AC自动机的运行原理：
**构建字典图实现自动跳转，构建失配指针实现多模式匹配。**
# 代码
```cpp
const int N=1000;
struct AC_automaton{
int tr[N][26],cnt;//TRIE
int e[N];//标记字符串结尾
int fail[N];//fail指针
void insert(char * s){//插入模式串
int p=0;
for(int i=0;s[i];i++){
int k=s[i]-'a';
if(!tr[p][k])tr[p][k]=++cnt;
p=tr[p][k];
}
e[p]++;
}
void build(){
queue<int>q;
memset(fail,0,sizeof(fail));
for(int i=0;i<26;i++)if(tr[0][i])q.push(tr[0][i]);
//首字符入队
//不直接将0入队是为了避免指向自己
while(!q.empty()){
int k=q.front();q.pop();//当前结点
for(int i=0;i<26;i++){
if(tr[k][i]){
fail[tr[k][i]]=tr[fail[k]][i];//构建当前的fail指针
q.push(tr[k][i]);//入队
}
else tr[k][i]=tr[fail[k]][i];
//匹配到空字符，则索引到父节点fail指针对应的字符，以供后续指针的构建
//类似并差集的路径压缩，把不存在的tr[k][i]全部指向tr[fail[k]][i]
//这句话在后面匹配主串的时候也能帮助跳转
}
}
}
int query(char *t){
int p=0,res=0;
for(int i=0;t[i];i++){
p=tr[p][t[i]-'a'];
for(int j=p;j&&~e[j];j=fail[j])res+=e[j],e[j]=-1;
}
return res;
}
};
AC_automation ac;
```
[1]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/2858847684.gif
[2]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/3946915055.png
[3]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/1745118561.gif
[4]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/1426947356.png
[5]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/1085042377.png
[6]: https://hexo-source-1257756441.cos.ap-chengdu.myqcloud.com/2018/08/24151497.gif