KMP 算法探究

本文探究了KMP算法及其基础应用

写在前面

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
2
3
4
5
6
7
8
9
10
void GetPi(char* p, int Pi[]) {
int n = strlen(p);
for (int i = 0; i < n; i++)
for (int j = 1; j <= i; j++) {
bool flag = true;
for (int k = 0; flag && k < j; k++)
if (p[k] != p[i - j + 1 + k]) flag = false;
if (flag) Pi[i] = j;
}
}

时间复杂度 $\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
2
3
4
5
6
7
8
9
void GetPi(char* p, int Pi[]) {
int n = strlen(p);
for (int i = 1; i < n; i++) {
int j = Pi[i - 1];
while (j && p[i] != p[j]) j = Pi[j - 1];
if (p[i] == p[j]) j++;
Pi[i] = j;
}
}

虽然这三个结论证明起来非常麻烦而抽象,但是代码实现起来却轻松而直观。

前缀函数将成为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
2
for (int i = 0; i < m; i++) num[Pi[i]]++;
for (int i = n - 1; i; i--) num[Pi[i - 1]] += num[i];

补充

注意到当主串和模式串相同,即询问模式串的每个前缀在自身中出现的次数时,可以直接对模式串本身求前缀函数。时间复杂度优化到 $\mathcal{O}(n)$。但因为前缀函数的特殊性,计算出现次数时会漏掉自己本身,所以需要最后统一对权值数组加一。