Theme NexT works best with JavaScript enabled

KMP 算法探究

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

写在前面

0xfaner 一直对KMP算法不甚熟悉,于是花了点时间查漏补缺。网上讲解KMP算法的文章大多杂乱无章质量低下表述不清自相矛盾(恼),给 0xfaner 的学习造成了很大的困扰。这里要鸣谢OI-wiki, 0xfaner 从中受了不少启发。

本来 0xfaner 对于这样简单的算法是没打算水一篇博文的,但学习的过程中不知不觉就整理好了,遂决定放到博客里,给其他对KMP算法有困扰的同学提供一点微小的帮助。其实是因为自己太菜了,学了好久才学会。

本文将随 0xfaner 对 KMP 的理解而不断更新。

简介

KMP算法由 D.E.Knuth , J.H.MorrisV.R.Pratt 三人发现,[K]nuth-[M]orris-[P]ratt,这就是KMP名称的由来。

字符串问题在算法竞赛中有着重要的地位,而KMP是字符串问题中经典的单模匹配(即只有一个模式串的模式匹配)算法。

前缀函数

首先给出几个定义:

  • $ str(i,j) $ 表示字符串 $ p $ 第 $ i $ 位到第 $ j $ 位的子串。
  • $ p[i] $ 表示字符串 $ p $ 的第 $ i $ 位字符。
  • $ \pi(i) $ 表示对于字符串 $ p $ ,满足既是 $ str(0,i) $ 的真前缀同时也是该子串的后缀的前缀长度。

一个字符串的真前缀是其前缀但不等于该字符串自身,否则对于任意 $ i \in [0,n) $ 有 $ \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) $ 。但因为前缀函数的特殊性,计算出现次数时会漏掉自己本身,所以需要最后统一对权值数组加一。