写在前面
0xfaner 一直对 KMP 算法不甚熟悉,于是花了点时间查漏补缺。而网上讲解 KMP 算法的文章大多杂乱无章质量低下表述不清自相矛盾(恼),给 0xfaner 的学习造成了很大的困扰。这里要鸣谢 OI-wiki,0xfaner 从中受了不少启发。
本来 0xfaner 对于这样简单的算法是没打算水一篇博文的,但学习的过程中不知不觉就整理好了,遂决定放到博客里,给其他对 KMP 算法有困扰的同学提供一点微小的帮助。其实是因为自己太菜了,学了好久才学会。
本文将随 0xfaner 对 KMP 的理解而不断更新。
简介
KMP 算法由 D.E.Knuth , J.H.Morris 和 V.R.Pratt 三人发现,[K]nuth-[M]orris-[P]ratt,这就是KMP名称的由来。
字符串问题在算法竞赛中有着重要的地位,而 KMP 是字符串问题中经典的单模匹配(即只有一个模式串的模式匹配)算法。
而要学会 KMP 算法,我们首先要理解前缀函数。前缀函数是 KMP 算法的核心,理解了前缀函数后,我们可以非常轻松的理解 KMP。
前缀函数
首先给出几个定义:
$str(i,j)$ 表示字符串 $p$ 第 $i$ 位到第 $j$ 位的子串。
$p[i]$ 表示字符串 $p$ 的第 $i$ 位字符。
$\pi(i)$ 表示对于字符串 $p$,满足既是 $str(0,i)$ 的真前缀同时也是该子串的后缀的前缀长度。
一个字符串的真前缀是其前缀但不等于该字符串自身,否则恒有 $\pi(i)=i+1$。
那么可以给出 $\pi(i)$ 的定义:
$\pi(i)=\max\{j|str(0,j-1)=str(i-(j-1),i)\And j\leq i\}$。
例如,字符串 $AABAAAB$ 的前缀函数值依次为 $0,1,0,1,2,2,3$,给出各自的图示:
图中红色部分表示对应相等的最长前缀,容易发现 $\pi(0)=0$ 必然成立。
暴力
可以写出暴力代码:
1 | void GetPi(char* p, int Pi[]) { |
时间复杂度 $\mathcal{O}(n^3)$,考虑优化。
优化
第一个结论
$\pi(i) \leq \pi(i-1) +1$
假设 $\exists i\in [1,n)$,使得 $\pi(i)>\pi(i-1)+1$
依据 $\pi(i)$ 定义有:$str(0,\pi(i)-1) = str(i+1-\pi(i),i)$
两串同时删去右端点:$str(0,\pi(i)-2) = str(i+1-\pi(i),i-1)$
依据定义有:$\pi(i-1) \geq \pi(i) -1$,这与 $\pi(i) >\pi(i-1) +1$ 相悖。
第二个结论
若 $p[i] = p[\pi(i-1)]$,那么有 $\pi(i) = \pi(i-1)+1$
首先依据 $\pi(i-1)$ 定义有:$str(0,\pi(i-1)-1) = str(i-\pi(i-1),i-1)$
若 $p[i] = p[\pi(i-1)]$,那么有:$str(0,\pi(i-1)) = str(i-\pi(i-1),i)$
依据定义有:$\pi(i) \geq \pi(i-1) + 1$
又因为第一个结论:$\pi(i) \leq \pi(i-1) + 1$
所以有:$\pi(i) = \pi(i-1) + 1$
最终结论
首先依据公式重新描述一下我们的目标:
找到最大的 $j$,使得 $str(0,j-1) = str(i-j,i-1)$,且 $p[i]=p[j]$(这样就有 $\pi(i)=j+1$)
发现依据 $\pi(i-1)$ 定义有:$str(0,\pi(i-1)-1) = str(i-\pi(i-1),i-1)$
易知 $p[i] \neq p[\pi(i-1)]$ 时有 $j = \pi(i)-1\leq \pi(i-1)$
那么 $str(i-j,i-1) = str(\pi(i-1)-j,\pi(i-1)-1)$
问题转化为:找到最大的 $j$,使得 $str(0,j-1) = str(\pi(i-1)-j,\pi(i-1)-1)$,且 $p[i]=p[j]$(这样就有 $\pi(i)=j+1$)
发现满足 $str(0,j-1) = str(\pi(i-1)-j,\pi(i-1)-1)$ 的最大的 $j$ 就是 $\pi(\pi(i-1)-1)$
此时若 $p[i] \neq p[\pi(\pi(i-1)-1)]$,那么问题又和上面的 $s[i] \neq s[\pi(i-1)]$ 类似,容易知道下一个满足条件的 $j=\pi(\pi(\pi(i-1)-1)-1)$ ……
于是 $j$ 可以被描述为 $\pi(\pi(\pi(\dots)-1)-1)$ 这样的结构,我们只需要不断地递归下去,直到 $p[i]=p[j]$ 或者 $j=0$ 为止。
而我们知道 $\pi(i) \leq i$。所以这种递归至多 $i$ 次就会停止。而在整体过程中 $\pi(i-1) \rightarrow \pi(i)$ 的值的下降数值不会超过上升数值,而上升数值至多为 $n$,所以整体时间复杂度仍是 $\mathcal{O}(n)$ 的。
代码如下:
1 | void GetPi(char* p, int Pi[]) { |
虽然这三个结论证明起来非常麻烦而抽象,但是代码实现起来却轻松而直观。
前缀函数将成为KMP算法的核心。
经典应用
查找子串
问题描述
给定主串 $s$ 与模式串 $p$,询问你模式串在主串中的全部出现位置。
如主串 $ABABA$,模式串 $ABA$,那么模式串在主串的 $[0,2]$ 与 $[2,4]$ 两区间的对应位置出现。
解法
假定主串长度为 $n$,模式串长度为 $m$。
那么让模式串在前,主串在后,两串拼接构造一个新串,那么这个新串的长度为 $m$ 的前缀即为模式串。
我们可以 $\mathcal{O}(n+m)$ 地算出这个串的前缀函数,其中若有 $\pi(i)=m$,说明区间 $[i-m+1,i]$ 对应的子串和模式串相同,当 $i-m+1 \geq m$ 时,区间 $[i-m+1,i]$ 对应的字符串完全落在主串内。也就代表着我们在主串中找到一个模式串。
时间复杂度 $\mathcal{O}(n+m)$。
补充
其中可以强行令 $\pi(m)=0$,即令主串的第一个字符的前缀函数值为 $0$。这样即可略去判断 $i-m+1 \geq m$ 的过程。当 $i \geq m$ 时只要 $\pi(i)=m$,就说明新串中区间 $[i-m+1,i]$ 对应了一次匹配。形象地理解,就是在模式串与主串中间用一个特殊字符隔开,使得主串的前缀函数对应的后缀都不会包括模式串。
注意到正常做需要 $\mathcal{O}(n+m)$ 的空间复杂度,在一部分毒瘤题中可能会卡空间,假定我们已知前缀函数的最大可能取值为 $k$(由前缀函数的性质可知 $k < m$),那么我们只需记录前缀函数前 $k$ 个值即可,空间复杂度优化到 $\mathcal{O}(k)$。
统计每个前缀出现次数
问题描述
给定主串 $s$ 与模式串 $p$,询问你模式串的每个前缀在主串中的出现次数。
如主串 $AABAAAB$,模式串 $AAAB$,那么模式串共有 $AAAB$,$AAA$,$AA$,$A$ 四个前缀,它们在主串中分别出现了 $1,1,3,5$ 次。
解法
模仿查找子串中的操作,求出主串 $s$ 对应的前缀函数,容易知道每一个 $\pi(i)$ 对应了多次模式串的前缀在主串中的出现,长度分别是 $\pi(i),\pi(\pi(i)-1),\pi(\pi(\pi(i)-1)-1)\dots$。
那么首先求出所有的 $\pi(i)$,记录到权值数组中,然后对于每一个 $\pi(i)$ 累加它的上层的贡献即可($\pi(n-1)$ 无上层贡献)。
时间复杂度 $\mathcal{O}(n+m)$。
代码形如:
1 | for (int i = 0; i < m; i++) num[Pi[i]]++; |
补充
注意到当主串和模式串相同,即询问模式串的每个前缀在自身中出现的次数时,可以直接对模式串本身求前缀函数。时间复杂度优化到 $\mathcal{O}(n)$。但因为前缀函数的特殊性,计算出现次数时会漏掉自己本身,所以需要最后统一对权值数组加一。