Theme NexT works best with JavaScript enabled

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是字符串问题中经典的单模匹配（即只有一个模式串的模式匹配）算法。

前缀函数

首先给出几个定义：

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