第 05 讲

串:朴素匹配与 KMP

串(字符串)是最贴近日常的线性结构,而「在一个大串里找一个子串」是编译器、编辑器、搜索引擎、 DNA 比对都在反复做的事。本章从最朴素的暴力匹配讲到 KMP 的「会用」:知道 next 表示什么、会套 0 基模板即可,不要求手推。

预计 120 分钟 前置:第 02 讲线性表、第 01 讲大 O 关键词:模式匹配 · next 数组 · 前缀函数
本章导读
  • 5.1 串的定义与术语 —— 打地基,尤其要弄清「子串、前缀、后缀」的严格定义。
  • 5.2 朴素模式匹配 —— 看懂它慢在哪里,才能明白 KMP 在优化什么。
  • 5.3 KMP 算法 —— 本章最关键:理解 next 表示「失配后跳到哪」,会用 0 基模板;不要求手推。
  • 5.4 KMP 的 0 基实现与复杂度。
  • 5.5 最常见的写法错误:回退写成 len-- 为什么会退化。
  • 5.6 朴素匹配 vs KMP 的对比。

5.1 串是什么:定义与术语

5.1.1 定义与术语

串(String),又称字符串,是由零个或多个字符组成的有限序列,记作 S = "a1a2…an"。其中 n 是串的长度; 长度为 0 的串叫空串,记作 "" 或 Ø。

串在逻辑上是一种特殊的线性表——数据元素被限定为字符。但串的操作通常不是「取第 i 个元素」, 而是整段比较、查找、拼接。所以串有一套自己的术语。下面统一用 S = "data" 举例;位置从 0 开始数。

(1)一张表把术语对齐

术语严格定义以 "data" 为例最容易错在哪
串长 字符的个数 n "data" 的长度是 4 空格也是字符,算长度
空串 长度 n = 0 的串,里面一个字符也没有 "" 空串 不是 空格串
空格串 由一个或多个空格组成的串,长度 ≥ 1 " " 的长度是 1 看不见,但它不是空串
子串 原串中连续的一段字符 "dat"、"ata"、"a" 必须连续;"dta" 不是子串
真子串 子串,且不等于原串本身 "dat"、"ata"、"" “真”只排除原串,不排除空串
主串(目标串 / text) 被搜索的那个大串,通常记作 S S = "data" 本课件统一:主串 = 目标串 = 被搜索的串
模式串(pattern) 要在主串里查找的那个串,通常记作 P P = "ata" 模式串不一定比主串短,但匹配时通常 m ≤ n
前缀 从 S[0] 开始、长度为 k 的连续段,k = 0…n ""、"d"、"da"、"dat"、"data" 一定从第一个字符开始,不能从中间开始
真前缀 前缀,且不等于原串,即 k = 0…n−1 ""、"d"、"da"、"dat" KMP 的 border 只用真前缀
后缀 以 S[n−1] 结尾、长度为 k 的连续段,k = 0…n ""、"a"、"ta"、"ata"、"data" 一定以最后一个字符结尾,方向别写反
真后缀 后缀,且不等于原串,即 k = 0…n−1 ""、"a"、"ta"、"ata" KMP 的 border 只用真后缀
串相等 长度相同,且对应位置的字符全部相同 "data" ≠ "Data" 大小写、空格都敏感

(2)放到模式匹配里看

在主串 S = "data structure" 里找模式串 P = "ata":

S = d a t a ···
P = a t a

P 第一次出现的位置是下标 1(从 0 开始数)。 所以模式匹配可以一句话说成:在主串 S 里,找模式串 P 第一次出现的起始下标。 后面第 5.2 节的朴素匹配、5.3 节的 KMP,都是在优化“怎么找”这件事。

(3)最容易混的三组概念

① 子串 vs 子序列 子串必须连续:"abc" 的子串有 "bc",但没有 "ac"。
子序列只要求相对顺序不变,可以不连续:"ac" 是 "abc" 的子序列。 这是 KMP(连续匹配)与 LCS 最长公共子序列(不连续)的分水岭。
② 空串 vs 空格串 "" 是空串,长度 0,里面没有字符;" " 是空格串,长度 1,里面有一个空格。 考试里“空串的长度是多少”“空格串是不是空串”都是送分题,但每年都有人错。
③ 前缀 / 后缀 vs 真前缀 / 真后缀 前缀、后缀都允许等于原串本身(k = n);真前缀、真后缀则要求 k < n,也就是把“整个串”排除掉。

(4)为什么 KMP 一定要用「真」前后缀

以 P = "ABAB" 为例:

所以 π[3] = 2;KMP 的 next / π 数组存的是这个 长度 2,不是字符串 "AB"。失配时,模式串直接跳到“长度为 2 的前缀”后面继续比, 主串指针 i 不用回退。

如果允许「整个串」会怎样? 任何串都等于它自己,最长相等前后缀就永远是原串,长度恒为 |P|。 失配后模式串“原地不动”,KMP 就退化成了朴素匹配。所以 border 必须排除 |P| 本身, 这也是“真前缀 / 真后缀”里“真”字的全部意义。
关于空串的约定 本课件把空串也算作子串、前缀、后缀(长度 0),这样 π[0] = 0 和“没有非空 border”能统一表示。 如果你们的教材规定“前缀/后缀必须非空”,把长度 0 的那一项去掉即可,KMP 的结论不变。

5.2 朴素模式匹配:暴力法慢在哪

5.2.1 算法思路

模式匹配(pattern matching)问题可以严格描述为:给定主串 S(长度 n)与模式串 P(长度 m,通常 m ≤ n),求 P 在 S 中第一次出现的位置(下标), 不存在则返回 -1。

最直觉的做法是枚举所有可能的对齐位置:让 P 的左端依次对齐 S 的 第 0、1、2、…、n−m 位,每个位置从 P[0] 开始逐字符比较,全部相同则匹配成功。这个方法叫 朴素匹配(Naive / Brute-Force / BF)。

#include <iostream>
#include <string>
using namespace std;

/* 朴素模式匹配:返回 P 在 S 中第一次出现的下标,找不到返回 -1
   设 n = |S|, m = |P|
   最好:第一个位置就匹配           O(m)
   最坏:每轮都比到最后一个字符才失败  O((n-m+1)*m) ≈ O(n*m) */
int naiveIndex(const string& S, const string& P) {
    int n = S.size(), m = P.size();
    if (m == 0) return 0;
    for (int pos = 0; pos + m <= n; ++pos) {     // 枚举每一个对齐位置
        int j = 0;
        while (j < m && S[pos + j] == P[j]) ++j;   // 逐个字符比对
        if (j == m) return pos;                  // 全部相等 → 命中
    }
    return -1;
}

int main() {
    string S = "ABABABCABABABCABA";
    string P = "ABABCABA";
    cout << naiveIndex(S, P) << "\n";   // 2
    return 0;
}

5.2.2 亲手看它一步步怎么比

下面的动画用同一组主串与模式串演示朴素匹配的每一次比较,注意观察失配后指针是怎么动的:

观察重点:本轮起点 start 只增不减;第一次失配后,模式串右移一格, start 从 0 变成 1。当前比较位置 i 则从失配处回到新起点 1, j 归零。所谓“i 回溯”,回退的是这个当前比较位置,不是外层起点。

5.2.3 复杂度分析:为什么慢

设 n = |S|,m = |P|:

5.3 KMP 算法与 next 数组的作用

5.3.1 一句话本质:最长相等真前后缀重新对齐

KMP = 「主串指针 i 只前进不后退」 + 「失配时把模式串滑动到最长相等真前后缀重新对齐」

关键词是“最长”:不是随便找一个相等前后缀,而是找 P[0..j-1] 的 最长相等真前后缀,长度记为 k。k 越大,保留的已匹配字符越多, 模式串需要移动的格数 j−k 越小;取最长才能既不漏掉可能的匹配,又尽量少比。

KMP 由 Knuth、Morris、Pratt 三人于 1977 年提出,因此得名。它的核心洞察是:

假设我们已经匹配了 P[0..j-1] 这 j 个字符,主串中对应的那段就是 S[i-j .. i-1], 它恰好等于 P[0..j-1]。现在 S[i] ≠ P[j] 失配了。 朴素做法要放弃这段匹配重新开始,但既然主串里那段就等于 P[0..j-1], 我们完全可以问:在 P[0..j-1] 内部,最长的「开头 = 结尾」有多长? 如果有,长度是 k,那么主串里那段匹配内容的最后 k 个字符,一定等于模式串的前 k 个字符。 于是我们不必移动 i,只需要把模式串向右滑,让 P[0..k-1] 对准主串刚才那段的后 k 个字符, 即令 j = k,继续比较。

“最长”到底怎么选:以已匹配的 “ABAB” 为例
  • 相等真前后缀有 "" 和 "AB";最长非空的是 "AB",所以 k = 2。
  • 若取更短的 k = 1("A"),模式串要右移 j−k = 3 格, 比最长 border 多滑 1 格;这一步可能直接跳过某个可行的匹配起点,而且只保留了 "A",丢掉了已经确认的 "AB" 这段更长匹配。
  • 长度为 3 的 "ABA" 根本不是 "ABAB" 的后缀,不能取;取错会漏匹配。
  • 所以取 k = 2:模式串右移 j−k = 4−2 = 2 格,令 j = 2,i 不动。
失配时(j > 0):k = 最长相等真前后缀长度(0 ≤ k < j) → j ← k,i 不变
主串 S A B A B C … i 指向这里,S[i]='C' 与 P[4]='A' 失配 模式串 P A B A B 已匹配 j = 4 个字符 这一段 P[0..3] = "ABAB" 与主串完全相同 前缀 "AB" 后缀 "AB" 最长相等前后缀 → k = 2,于是让 j = 2,i 不动 滑动后 A B A B C P[0..1] 已经对齐好了,直接从 P[2] 继续比即可,i 不用回退 注意:模式串是"整体向右滑动 2 格",等价于 j 从 4 变成 2;主串指针 i 原地不动。
图 5-2 KMP 的核心思想:失配时利用最长相等真前后缀重新对齐

5.3.2 next 数组的定义(0 基前缀函数 π)

本课件只采用一种约定:0 基前缀函数 π。有些书把它叫 next, 名字不同,但本章里数组的含义固定为下面这一种,不再引入其他下标约定。

π[i]
P[0..i] 的最长相等真前后缀的长度。
π[0]
恒为 0:单个字符没有真前后缀。
取值范围
0 ≤ π[i] ≤ i。注意存的是长度,不是字符串,也不是下标。
失配时
当前在 P[j] 失配:
  • j > 0:令 j = π[j-1],i 不动;
  • j == 0:模式串第一位就失配,只能让 i++。
iP[0..i]最长相等真前后缀π[i]
0"A"无(空串)0
1"AB"无(空串)0
2"ABA""A"1
3"ABAB""AB"2

例:P = "ABAB" 时,π = [0, 0, 1, 2]。 所以 π 数组可以理解为:每个前缀的“最长 border 有多长”。 5.4.1 的模板就是按这个定义写的。

手推从略 next / π 只要求理解「失配后模式串跳到哪」、会用 0 基模板; 不要求手推 π 的构造过程。

5.3.3 KMP 匹配全过程

有了 π 数组,匹配过程就极其简单:i 只增不减;失配时若 j > 0 就 j = π[j-1],否则 i++。下面的动画把 i、j、 模式串的对齐位置、以及每次 j 的回退都标了出来:

考点:KMP 的比较次数 KMP 的比较次数是 O(n + m),但要注意——它并不保证「比较次数一定比朴素算法少」。 对于某些输入(例如模式串首字符几乎不出现在主串中),朴素算法反而可能比较得更少。 KMP 的价值在于最坏情况下也稳定是 O(n+m),不会退化到 O(n×m)。

5.3.4 什么时候用 KMP:匹配场景与朴素算法对比

前面说了 KMP 最坏是 O(n+m)、朴素是 O(n×m)。但在真实数据上,朴素算法并不总是慢。 下表给出几种典型输入下两个算法的比较次数感受(n = 10000,m = 100):

主串特征模式串(m = 100)朴素比较次数(约)KMP 比较次数(约)差距(朴素 / KMP)
随机小写字母随机 100 字符≈ 1.04n = 10,400≈ n + m = 10,100≈ 1.0×
全 'a'"a…ab"(99 个 a + b)≈ 100n = 1,000,000≈ 2n = 20,000≈ 50×
全 'a'"ba…a"(b + 99 个 a)≈ n = 10,000≈ n + m = 10,100≈ 1.0×(朴素略快)
周期串 "ababab…""(ab)…ac"(49 组 ab + ac)≈ 50n = 500,000≈ 2n = 20,000≈ 25×
被刻意构造的恶意数据—退化到 O(n×m) = 1,000,000始终 O(n+m) ≤ 20,000≈ 50×

在 n = 10000、m = 100 这组参数下,最坏差距约 50 倍; 但随机文本上两者几乎一样,甚至 "ba…a" 这种输入朴素还略快。 所以 KMP 不是“永远更快”,而是“最坏情况有保证”。

结论:KMP 的价值在于「最坏情况的上界」与「主串只扫描一遍」。 当主串是流式到达、不能回退(例如网络数据包逐字节到达)时,KMP 是唯一可行的线性算法; 而朴素算法需要回头重看数据,天然不适用于流式场景。

5.4 KMP 的完整实现与优化

5.4.1 0 基前缀函数版(本章写法)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

/* ============================================================
   KMP(0 基下标,π 数组约定)
   pi[i] = P[0..i] 的最长相等真前后缀长度
   ============================================================ */

/* 求前缀函数,时间复杂度 O(m),空间 O(m) */
vector<int> prefixFunction(const string& P) {
    int m = P.size();
    vector<int> pi(m, 0);
    for (int i = 1; i < m; ++i) {
        int len = pi[i - 1];                 // 先继承前一位的结果
        while (len > 0 && P[i] != P[len]) {  // 对不上就回退到次优候选长度
            len = pi[len - 1];
        }
        if (P[i] == P[len]) ++len;           // 能接上就 +1
        pi[i] = len;
    }
    return pi;
}

/* 返回 P 在 S 中第一次出现的下标,找不到返回 -1 */
int kmpSearch(const string& S, const string& P) {
    int n = S.size(), m = P.size();
    if (m == 0) return 0;
    vector<int> pi = prefixFunction(P);
    int j = 0;                               // j = 当前已匹配的字符个数
    for (int i = 0; i < n; ++i) {            // i 只前进,永不回退
        while (j > 0 && S[i] != P[j]) j = pi[j - 1];
        if (S[i] == P[j]) ++j;
        if (j == m) return i - m + 1;        // 全部匹配,返回起始下标
    }
    return -1;
}

int main() {
    string S = "ABABABCABABABCABA";
    string P = "ABABCABA";
    vector<int> pi = prefixFunction(P);
    for (int x : pi) cout << x << ' ';
    cout << "\n";                            // 0 0 1 2 0 1 2 3
    cout << kmpSearch(S, P) << "\n";         // 2
    return 0;
}

注意代码里的 while (j > 0 && S[i] != P[j]) j = pi[j - 1];。 为什么 j 回退的总次数是 O(n)?做个均摊分析:

因此总回退次数 ≤ 总减少量 ≤ 总增加量 ≤ n,回退是 O(n) 的。 再加上 while 条件本身每轮只多检查常数次,匹配循环的比较次数是 n + O(n) = O(n);最后加上预处理 π 的 O(m), KMP 总复杂度是 O(n + m)。

5.4.2 KMP 的复杂度与局限

复杂度

  • 时间:预处理 O(m) + 匹配 O(n) = O(n+m)。
  • 空间:O(m) 存 π 数组(可优化到 O(m) 以下?不行,最少也要 O(m))。
  • 优点:最坏情况有保证;只依赖模式串的预处理结果,可复用。

局限

  • 每次失配只把模式串滑动一小段,平均性能不如更复杂的专用算法。
  • 对多模式匹配(同时找很多关键字)无能为力 → 需要 AC 自动机。
  • 实现细节容易写错(下标约定、哨兵值),考试时优先手推验证。

5.5 最常见的写法错误:回退写成了 len--

求 π 时,很多同学把「对不上就缩短候选长度」直觉地写成 --len,然后重试。 这样结果是对的,复杂度却退化成 O(m²)——因为它把「按前缀函数跳跃」 换成了「一格一格地挪」。

正确的写法只有一种:len = pi[len - 1]。 也就是失配时直接跳到「当前候选前缀的最长 border」,而不是让长度每次只减 1。

一个用例就能判断 看 P = "aaaa…a"(10 万个 a): 正确写法是线性的、瞬间出结果;写成 len-- 会慢到跑不完。 如果你在本地跑这个用例超时,基本就是回退写错了。

5.6 朴素匹配 vs KMP

对比项朴素匹配 BFKMP
当前比较位置 i 是否回退(是否重复扫描)会回退不回退
预处理无求 π:O(m)
时间复杂度(最坏)O(n×m)O(n+m)
额外空间O(1)O(m)
适用场景短模式串、教学最坏情况有保证
怎么选?
  • 考试 / 面试:KMP 的 next 数组作用要会说,0 基模板要会套;不要求手推。
  • 竞赛:KMP 是基础工具;更复杂的多模式匹配再学 AC 自动机。
  • 工程:先用 std::string::find,性能不够再换专用算法。