串:朴素匹配与 KMP
串(字符串)是最贴近日常的线性结构,而「在一个大串里找一个子串」是编译器、编辑器、搜索引擎、 DNA 比对都在反复做的事。本章从最朴素的暴力匹配讲到 KMP 的「会用」:知道 next 表示什么、会套 0 基模板即可,不要求手推。
- 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":
P = a t a
P 第一次出现的位置是下标 1(从 0 开始数)。
所以模式匹配可以一句话说成:在主串 S 里,找模式串 P 第一次出现的起始下标。
后面第 5.2 节的朴素匹配、5.3 节的 KMP,都是在优化“怎么找”这件事。
(3)最容易混的三组概念
"abc" 的子串有 "bc",但没有 "ac"。子序列只要求相对顺序不变,可以不连续:
"ac" 是 "abc" 的子序列。
这是 KMP(连续匹配)与 LCS 最长公共子序列(不连续)的分水岭。
"" 是空串,长度 0,里面没有字符;" " 是空格串,长度 1,里面有一个空格。
考试里“空串的长度是多少”“空格串是不是空串”都是送分题,但每年都有人错。
k = n);真前缀、真后缀则要求
k < n,也就是把“整个串”排除掉。
(4)为什么 KMP 一定要用「真」前后缀
以 P = "ABAB" 为例:
- 真前缀:
""、"A"、"AB"、"ABA"; - 真后缀:
""、"B"、"AB"、"BAB"; - 两边相等的最长非空串是
"AB",长度 2。
所以 π[3] = 2;KMP 的 next / π 数组存的是这个
长度 2,不是字符串 "AB"。失配时,模式串直接跳到“长度为 2 的前缀”后面继续比,
主串指针 i 不用回退。
|P|。
失配后模式串“原地不动”,KMP 就退化成了朴素匹配。所以 border 必须排除 |P| 本身,
这也是“真前缀 / 真后缀”里“真”字的全部意义。
π[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|:
- 最好情况:第一轮就匹配成功,比较 m 次,
O(m)。 - 最坏情况:每一轮都要比到模式串的最后一个字符才失败。典型输入如
S = "aaaaaaaaaab",P = "aaab"。此时每个对齐位置要比较 m 次, 共(n-m+1)个位置,总计约m(n-m+1) ≈ O(n×m)。 - 平均情况:若字符随机,每轮平均比较次数是常数
1/(1-σ)(σ 为字符出现概率), 总体接近O(n)。所以朴素算法在自然文本上并不算太差——但在 大量重复字符(DNA、二进制串、恶意构造的输入)面前会退化到平方级。
5.3 KMP 算法与 next 数组的作用
5.3.1 一句话本质:最长相等真前后缀重新对齐
关键词是“最长”:不是随便找一个相等前后缀,而是找 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,继续比较。
- 相等真前后缀有
""和"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不动。
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++。
i | P[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 的回退都标了出来:
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)?做个均摊分析:
j从 0 开始,且始终≥ 0;- 每轮外层 for(每个主串字符)最多执行一次
++j, 所以 n 轮最多增加 n; - 每次
while回退执行j = pi[j - 1],因为pi[j - 1] ≤ j - 1,所以j至少减少 1。
因此总回退次数 ≤ 总减少量 ≤ 总增加量 ≤ 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
| 对比项 | 朴素匹配 BF | KMP |
|---|---|---|
当前比较位置 i 是否回退(是否重复扫描) | 会回退 | 不回退 |
| 预处理 | 无 | 求 π:O(m) |
| 时间复杂度(最坏) | O(n×m) | O(n+m) |
| 额外空间 | O(1) | O(m) |
| 适用场景 | 短模式串、教学 | 最坏情况有保证 |
- 考试 / 面试:KMP 的 next 数组作用要会说,0 基模板要会套;不要求手推。
- 竞赛:KMP 是基础工具;更复杂的多模式匹配再学 AC 自动机。
- 工程:先用
std::string::find,性能不够再换专用算法。