AC自动机学习笔记

· · 个人记录

AC自动机学习笔记

(以下内容皆为作者初学AC自动机的粗浅理解，若有王腾还请见谅)

-1.前置芝士

作为字符串专题中进阶内容，AC自动机的前置包括KMP和Trie(字典树)。

0.自动机的定义

自动机，说白了就是一个有向图，但节点被称为状态，边被称为转移。传统意义上来说，自动机上会有一个指针，位于一个状态，每次改变状态需要通过有向边转移。当然，一些阴间题目可以直接给你搞成图论题，就很离谱。

1.AC自动机的作用

AC自动机主要可以解决多模式串匹配问题。考虑KMP，KMP只能对一个模式串进行O(n)的匹配，但是AC自动机可以借助Trie，实现对多个模式串的匹配，复杂度也可以维持在O(n)，也不需要开辟比KMP更多的空间（复杂度意义上）。如此强大的数据结构，自然是众多蒟蒻向字符串进阶冲击的第一个大知识点。

2.多模匹配的基本思路

我们反观KMP，注意到其核心思想在于重复利用已经匹配过的信息，利用nxt数组，KMP可以回溯到上一个可利用的位置，从而优化复杂度。那么对于多模匹配，我们是否可以采用相同的思路呢？

是可以的！我们所需要维护的是每一个模式串子串的最长后缀，使得它是某个模式串的前缀。但是这时，我们显然不能使用KMP的方法，毕竟存在多个子串，求nxt数组必须使用其他的方法。我们深入思考一下KMP的求nxt方法，就可以发现它的一个关键点：

nxt[s[i]+c]=s[nxt[i]]+c

前提是s[nxt[i]+1]=c。 我们可以照搬这个重要结论，就可以解决问题了！

桥豆麻袋，这和Trie和自动机有啥关系？

3.Trie的引入

如果仔细想想的话，你会发现上述思路并不是完全正确的。如果一个字符串失配，不一定要去直接跳转到nxt[i],可能在另外一个模式串里字符没有失配，这样每次匹配都要枚举每个字符串，复杂度退化至O(kn)。这时我们可以引入Trie了！我们发现，Trie的基本思路在于合并相同前缀，这正是我们所需要的！（其实，换一个角度来说，利用Trie进行字符串检索本质上就是一个自动机）此时，我们的思路已经很明了了：使用Trie进行字符串检索，在失配时使用nxt数组回到其中一个后缀，并重复以上过程。由于在匹配时始终位于一个状态（一个前缀位置），而在算法过程中状态不断地通过Trie的边和nxt数组进行转移，故被称为自动机。这也是为什么有句老话：AC自动机就是Trie上的KMP。

4.一些细节

虽然以上就是AC自动机的正确思路，但是在写代码的时候还是有很多实用的技巧来提升效率 ，避免TLE自动机的出现。

1.预处理失配

考虑到我们会反复经过同一个节点，我们可以通过预处理如果在这个节点遇到字符c需要跳转到哪里的方式来优化常数。方法就是通过bfs，由于nxt[i]必须为i的真后缀，其长度必然小于i，从而已经被bfs处理过了。

2.nxt树统计匹配

我们在统计匹配次数的时候必须考虑到当前匹配的所有存在的后缀。在匹配时，指针所在的状态是最长可匹配前缀，这意味着当匹配成功时，我们如果只计算当前的匹配数目，会落下当前匹配前缀的诸多后缀。举个栗子，对于匹配串“ab”,"aab","baab",当匹配到"baab"时，"ab"和"aab"也应该记上一次匹配。在此处，如果使用暴力跳nxt的方法就会复杂度爆炸。我们发现，匹配次数等同于节点在nxt树上的子树和，可以离线O（n）计算。

5.图示

咕咕咕……