0xfaner's Blog

Just something trivial

KMP 算法探究

Posted on In
Symbols count in article: 4.2k Reading time ≈ 4 mins.

本文探究了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)$。但因为前缀函数的特殊性，计算出现次数时会漏掉自己本身，所以需要最后统一对权值数组加一。