一步一步式弄懂 KMP 算法

问题描述

在开始学习 KMP 算法之前，先来看看我们的目标，即字符串搜索。

字符串搜索（String Searching），也称为模式匹配（Pattern Matching），是字符串应用中的一个基础问题：在一个较长的“主串”（text）中，查找一个较短的“模式串”（pattern）是否出现，以及出现的位置。

• 假设：
  • 主串：T，长度：ｎ
  • 模式串：P，长度：m
  • 目标：返回主串中第一个完全匹配模式串的第一个字符在主串中的下标，否则返回 -1；

朴素字符串匹配算法

朴素匹配（Naive / Brute-Force String Matching）是最简单、最直观的字符串查找方法：主串 T 和模式串 P，逐个位置对齐，逐字符比较。

• 📌 算法思想：
  • 从主串 T 的第 0 位开始，尝试匹配 P
  • 如果匹配失败，就主串指针只前进 1 位，重新从 P[0] 开始匹配
  • 重复直到找到匹配，或主串结束

// 朴素匹配int BFMatch1(const string& T, const string& P) {  if (T.length() < P.length()) return -1;   int n = T.length();  int m = P.length();  for (int i = 0; i <= n - m; i++) {    int j = 0;    while (T[i + j] == P[j] && j < m) {      j++;    }    if (j == m) return i;  }  return -1;     } // 朴素匹配的另一种实现（显式回退）int BFMatch2(const string& T, const string& P) {  if (T.length() < P.length()) return -1;    int n = T.length();  int m = P.length();  for (int i = 0, j = 0; i < n && j < m; i++) {    if (T[i] == P[j]) j++;    else { i -= j; j = 0; }  }  if (j == M) return i;  else return -1;}

KMP 简介

KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它的核心思想是：当匹配失败时，利用已匹配部分的信息，避免主串指针回溯，从而将时间复杂度从朴素算法的 $O(n·m)$ 降低到 $O(n + m)$。

K — Donald Knuth、M — James H. Morris、P — Vaughan Pratt，这三位学者在 1970 年各自独立地发现了这一高效的字符串匹配算法，并于 1977 年联合发表了经典论文。

在 KMP 算法中，最关键的一步是构建一个「前缀函数（prefix function）」数组（也常被称为部分匹配表 / next / pi / lsp 数组），可以说理解了前缀函数，就理解了 KMP 算法。

前缀函数中有一句代码（j = pi[j - 1]）是比较难理解的，很多人只记住了这句代码，没有彻底搞清楚它。接下来我们将一步一步来，构建前缀函数。

本文主要参考了：https://oi-wiki.org/string/kmp/

前缀函数

前缀与后缀

• 前缀

  • 假设长度为 n 的字符串 S，它的前缀是指从字符串第一个字符开始到某个位置 $𝑖(i<=n)$ 结束的一个特殊子串。
  • 真前缀 指除了 S 本身的 S 的前缀。
  • 举例来说，字符串 abcabcd 的前缀为 {a, ab, abc, abca, abcab, abcabc, abcabcd}, 而它的真前缀为 {a, ab, abc, abca, abcab, abcabc}。

• 后缀

  • 假设长度为 n 的字符串 S，它的后缀是指从字符串某个位置 $𝑖(i<=n)$ 开始到字符串结尾的一个特殊子串。
  • 真后缀 指除了 S 本身的 S 的后缀。
  • 举例来说，字符串 abcabcd 的后缀为 {d, cd, bcd, abcd, cabcd, bcabcd, abcabcd}，而它的真后缀为 {d, cd, bcd, abcd, cabcd, bcabcd}。

前缀函数的定义

• 假设长度为 n 的字符串 S，其前缀函数被定义为一个长度为 n 的数组 𝜋 。 其中 𝜋[𝑖] 的定义是：
  • 𝜋[𝑖] 就是字符串 S[0, i] 的最长相等的真前缀与真后缀的长度。
  • 如果字符串 S[0, i]没有相等的真前缀与真后缀，那么 𝜋[𝑖] = 0。
  • 特别地，规定 𝜋[0] = 0 。

再次说明一下：「前缀函数（prefix function）」有很多的叫法，如经常被称为部分匹配表 / next / pi / lsp 数组，本质都是一样的。

举个例子：abcabcd

1. i = 0，特别规定 𝜋[0] = 0
2. i = 1，S[0, 1] = "ab"，没有相等的真前缀与真后缀，𝜋[1] = 0
3. i = 2，S[0, 2] = "abc"，没有相等的真前缀与真后缀，𝜋[2] = 0
4. i = 3，S[0, 3] = "abca"，最长相等的真前缀与真后缀为 "a"，𝜋[3] = 1
5. i = 4，S[0, 4] = "abcab"，最长相等的真前缀与真后缀为 "ab"，𝜋[4] = 2
6. i = 5，S[0, 5] = "abcac"，最长相等的真前缀与真后缀为 "abc"，𝜋[5] = 3
7. i = 6，S[0, 6] = "abcabcd"，没有相等的真前缀与真后缀，𝜋[6] = 0

计算前缀函数的朴素算法

• 一个朴素、暴力的计算前缀函数的算法思路是：
  • 对与每个位置 i，枚举 S[0, i] 的所有真前后缀，从最长的真前后缀开始往下逐个比较 s[0, k-1] 和 s[i-k+1, i]，找到满足最大真前后缀相等的 k。

// 计算前缀函数的朴素算法void PrefixFuction1(const string& S, vector<int>& pi) {  int n = S.length();  for (int i = 1; i < n; i++) {    for (int j = i; j >=0; j--) {      if (S.substr(0, j) == S.substr(i - j + 1, j)) {        pi[i] = j;        break;      }    }  }} // c++ 中字符串的 substr 方法的参数含义// 第一个参数表示起始位置，第二个参数表示要截取的字符个数string substr (size_t pos = 0, size_t len = npos) const;

• 时间复杂度：由于 S.substr(0, j) 的复杂度为 O(j)，所以这个算法的总的复杂度为 O(n^3)。

• 还是以 abcabcd 为例，当 i = 6，S[0, 6] = "abcabcd" 时：

  1. S.substr(0, 6) = "abcabc" 不等于 S[1, 6] = bcabcd 然后 j--
  2. S.substr(0, 5) = "abcab" 不等于 S[2, 5] = "cabcd" 然后 j--
  3. S.substr(0, 4) = "abca" 不等于 S[3, 4] = "abcd" 然后 j--
  4. S.substr(0, 3) = "abc" 不等于 S[4, 3] = "bcd" 然后 j--
  5. S.substr(0, 2) = "ab" 不等于 S[5, 2] = "cd" 然后 j--
  6. S.substr(0, 1) = "a" 不等于 S[6, 1] = "d" 然后 j--
  7. 此时 j = 0 将退出里层循环

计算前缀函数的算法优化

第一次优化

观察前缀函数会发现，对于前缀函数 𝜋[i] 的值，下一个前缀函数 𝜋[i + 1] 的值最多增加 1。所以比较 S[0, i] 的真前后缀时，我们不从最长的开始，而是从 𝜋[i - 1] + 1 开始。

• 以 abcabcd 当 i = 6，S[0, 6] = "abcabcd" 时为例：（我们不知道 𝜋[6] 是多少，但是知道它最大只可能是 𝜋[5] + 1，也就是 𝜋[6] 最大等于 4）
  1. S.substr(0, 4) = "abca" 不等于 S[3, 4] = "abcd" 然后 j--
  2. S.substr(0, 3) = "abc" 不等于 S[4, 3] = "bcd" 然后 j--
  3. S.substr(0, 2) = "ab" 不等于 S[5, 2] = "cd" 然后 j--
  4. S.substr(0, 1) = "a" 不等于 S[6, 1] = "d" 然后 j--
  5. 此时 j = 0 将退出里层循环

// 第一次优化void PrefixFuction2(const string& S, vector<int>& pi) {  int n = S.length();  for (int i = 1; i < n; i++) {    for (int j = pi[i - 1] + 1; j >=0; j--) {      if (S.substr(0, j) == S.substr(i - j + 1, j)) {        pi[i] = j;        break;      }    }  }}

时间复杂度：虽然最坏情况复杂度还是 $O(n^3)$ ，但是一般情况能到 $O(n^2)$。

第二次优化（最终优化）

在计算 𝜋[i] 时，我们已经知道𝜋[i - 1] 的值，假设这个值为 j，则 j 代表了 S[0, i - 1] 的最大相等的真前后缀长度，所以字符串 S[0, j - 1] 等于 S[i - j, i - 1]。

由于 S[0, j - 1] 等于 S[i - j, i - 1]，如果此时 S[j] 等于 S[i]，则 𝜋[i] = 𝜋[i - 1] + 1。如果 S[j] 不等于 S[i]，此时需要求字符串 S[0, j - 1] 的前缀和 S[i - j + 1, i] 的后缀相等的前后缀中的最大的值（不是真前后缀）。求这个最大值有技巧，可以说 KMP 算法神来之笔，我们看下面的代码。

• 还是以 abcabcd，当 i = 6，S[0, 6] = "abcabcd" 时为例：
  • 在计算 𝜋[i] 时，已经知道 𝜋[i - 1] = 3，即 S[0, i - 1] = "abcabc" 的最大相等的真前后缀长度为 3。
  • S[j] = S[3] = 'a' 不等于 S[i] = S[6] = 'd'
  • 求 S[0, j - 1] = S[0, 2] = "abc" 的前缀和 S[i - j + 1, i] = S[4, 6] = "bcd"的后缀相等的前后缀中的最大的值。
  • abc 的前缀为 {a, ab, abc}，bcd 的后缀为 {d, cd, bcd}
  • 没有相等的则 𝜋[6] = 0

// 第二次优化 void PrefixFunciton3(const string& S, vector<int>& pi) {  int n = S.length();  for (int i = 1; i < n; i++) {    int j = pi[i - 1];    while (S[i] != S[j] & j > 0) j = pi[j - 1];  // ???    if (S[i] == S[j]) j++;    pi[i] = j;  }}

读到第六行代码的 while (S[i] != S[j] & j > 0) 时，最直接暴力的想法就是挨个比较，但是这里却是 j = pi[j - 1];，它是正确的？表示什么意思？又是怎么来的？

在发生失配时，即 S[i] 不等于 S[j]（ j = 𝜋[i - 1]）时，我们可以推导出 𝜋[i] 的值为字符串 S[i - j, i]的最长相等的真前缀与真后缀的长度。推导过程：

但是根据这个信息，我们还是无法读懂 j = pi[j - 1];到底是什么意思。。。

换个思路思考，在失配时，可以得到 S[0, j - 1] 等于 S[i - j, i - 1] 的信息(j = 𝜋[i - 1])，我们接下来需要做的是，找到一个最大的 k(k < j) （这里需要说明的是 k 是满足条件的字符串的下标）使得：

$S[0, k-1]$ 是 $S[0, j-1]$ 的相等真前后缀，因此我们可以从最大的相等真前后缀开始比较，直到最小相等真前后缀。此时需要证明 $π[π[j]-1]$ 是 $S[0,j-1]$ 的次长相等真前后缀。

Border Lemma

Border（边界）的定义：对于字符串 S，如果 S[0, k-1] = S[n-k, n-1]（其中 n 是字符串长度），则称 S[0...k-1] 是 S 的一个 border（边界/真前后缀）。

Border Lemma（边界引理）：如果 u 是字符串 w 的 border，v 是 u 的 border，那么 v 也是 w 的 border。

这正是我们所需要的！

Border 的链式结构：由 Border Lemma，所有 border 形成一个链：

π[i] → π[π[i]-1] → π[π[π[i]-1]-1] → ... → 0

前缀函数的应用