KMP算法&AC自动机小记

KMP算法

考虑匹配A串和B串,在A串里去寻找B串。

暴力的匹配方法是O(n^{2})的,我们发现如果每次都去从头开始,那未免太费力不讨好了。

我们能否利用已有信息进行一点优化呢?答案是肯定的。

考虑我们A串匹配到iB串匹配到j,那么有A[i]=B[j],A[i+1]\neq B[j+1]

这个时候我们是想在B中找到一个最大的k\leq j满足B[1...k]=B[j-k+1...j],这样的话就可以继续保持我们现有的性质(即匹配)。这样的东西我们暂称为Next数组。

那么假设我们知道了Next数组,我们就可以用下面这样一段代码去完成匹配

那么,为什么他是线性的呢?

观察下j,最多只可能增加n次,那么整个程序的while循环最多会让jn次。均摊一下就O(n)啦。

其次,怎么去求Next数组呢?

不难发现Next实际上是一个自身匹配的过程,也就是说,我们可以用同样的做法去求。


例题1. UVA12604 Caesar Cipher

直接枚举偏移值,问题转化为求匹配次数,时间复杂度O(NM)。几乎是模板题。


例题2. UVA12467 Secret Word

我们考虑用反串去匹配原串,那么每次匹配的时候j就是i这个位置的答案。输出的时候要逆序输出。


例题3. CF 808G Anthem of Berland

f[i][j]表示考虑母串前i个字母,在模式串中的kmp值为j的方案数。直接转移即可。


AC自动机

在理解了KMP以后AC自动机变得异常简单,先考虑把所有串插入到trie树里。

那么我们匹配到某个节点,要返回的话,肯定是类似KMP的思想,最长相等前后缀。于是考虑对每个点记录一个fail指针。不断地回溯构造即可。