首页/数据结构/第 4 章 串
408 计算机学科专业基础 数据结构 第 4 章

串
模式匹配与 KMP

每年 0–1 道选择题,内容几乎只有 KMP:next / nextval 数组的手算、匹配过程中的指针位置与比较次数。

在一篇文章里找一个词,最笨的办法是逐位置去试,失败了就回到下一个位置重来。KMP 的聪明之处在于:失败时已经比对过的信息不浪费,主串指针一步也不后退。

3 个考点模块 1 个 KMP 模拟器 1 张图
j123456 Pabaabc next011223 nextval010213
00
复习策略

考频地图

★★★☆☆ 中频 选择题

本章几乎只考 KMP:求 next / nextval 数组、KMP 匹配时的比较次数或某次失配后的 j 值。手算 next 有固定方法,练 5 个模式串就熟了。

考点考频常见问法
串的存储★☆☆☆☆“串的块链存储”
朴素匹配★★☆☆☆“最坏比较次数”
next / nextval★★★★★“模式串的 next 数组是”
KMP 匹配过程★★★★☆“第二趟匹配从哪里开始”“共比较几次”
一句话:KMP 失配时主串指针不回退,模式串指针 j 跳到 next[j]。next[j] = P 的前 j − 1 个字符中“最长相等前缀和后缀”的长度 + 1(下标从 1 开始时)。
01
4.1 · 打基础

串的存储与朴素匹配

★★☆☆☆ 低频 选择题

串是内容受限的线性表(元素是字符)。存储方式:定长顺序存储(字符数组,超长截断)、堆分配存储(动态申请)、块链存储(每个结点存多个字符,存储密度 = 串值所占空间 ÷ 结点总空间)。

朴素(暴力)模式匹配

从主串每个位置开始,与模式串逐个比较;一旦失配,主串指针回退到本趟起点的下一个位置,模式串回到开头。

主串长 n,模式串长 m 最坏比较次数 ≈ (n − m + 1) × m → O(nm) 例:S = "aaaaaaab",P = "aab",几乎每趟都比到最后一个字符才失配
02
4.2 · 必考

KMP 与 next 数组

★★★★★ 必考 选择题

一、KMP 的核心想法

主串 S abaabaabc 模式 P abaabc 右移后 abaabc S[6] ≠ P[6] 失配 已经匹配的 abaab 里: 最长相等前后缀是 ab(长 2) → 主串里刚匹配的末尾 ab 一定等于 P 的开头 ab → 直接让 P[3] 对齐 S[6],从这里继续比较 next[6] = 2 + 1 = 3 主串指针 i 不回退,只有模式串指针 j 回退
图 4-1 失配时已匹配部分的信息不能浪费:利用“最长相等前后缀”,模式串一次右移多位,主串指针不回退。

二、手算 next 数组(下标从 1 开始)

  1. next[1] = 0,next[2] = 1(固定)。
  2. 对 j ≥ 3:看 P 的前 j − 1 个字符,找最长的“既是前缀又是后缀”的子串(不能是整串本身),长度为 k。
  3. next[j] = k + 1。
#
例:P = abaabc
next
j=1
固定
0
j=2
固定
1
j=3
前 2 个 "ab":前缀 a,后缀 b,不等 → k = 0
1
j=4
前 3 个 "aba":a = a → k = 1
2
j=5
前 4 个 "abaa":a = a,ab ≠ aa → k = 1
2
j=6
前 5 个 "abaab":ab = ab → k = 2
3

三、nextval:避免无效比较

若 P[j] == P[next[j]],那么在 j 处失配后跳到 next[j],比的还是同一个字符,必然再失配。于是继续往前跳:

nextval[1] = 0 j ≥ 2:若 P[j] == P[next[j]],nextval[j] = nextval[next[j]];否则 nextval[j] = next[j] 例:P = aaaab,next = 0 1 2 3 4,nextval = 0 0 0 0 4

四、复杂度

求 next 数组 O(m),匹配 O(n),总 O(m + n)。KMP 的优势在主串中存在很多“部分匹配”时才明显;一般情况下朴素算法实际也接近 O(n + m)。

  • 题目若约定下标从 0 开始,next[0] = −1,整体比 1 起的版本小 1。看清约定再作答。
  • 求 next[j] 看的是前 j − 1 个字符,不包括 P[j] 本身。
  • 最长相等前后缀不能是整个子串自身。
  • KMP 中主串指针 i 永不回退,这是它与朴素算法的根本区别。
03
实战

真题与自测

★★★☆☆ 收口 选择题

一、真题问法

问法 1(2015 真题改写):“已知字符串 S 为 abaabaabacacaabaabcc,模式串 t 为 abaabc,采用 KMP 算法匹配,第一次出现失配(s[i] ≠ t[j])时 i = j = 5,则下次开始匹配时 i 和 j 的值分别是?”→ 下标从 0 起时 next[5] = 2,所以 i = 5、j = 2。

问法 2(2019 真题改写):“设主串 T = abaabaabcabaabc,模式串 S = abaabc,采用 KMP 算法,到匹配成功为止,单个字符的比较次数是?”→ 在上面的模拟器里输入可得 10 次。

二、折叠自测

1. 模式串 ababaa 的 next 数组(下标从 1 开始)?

0 1 1 2 3 4。

2. 上题的 nextval?

0 1 0 1 0 4。

3. 朴素匹配最坏时间复杂度?KMP 呢?

朴素 O(nm);KMP O(n + m)。

4. KMP 失配时主串指针怎么移动?

不动;只把模式串指针 j 改为 next[j](若为 0,则 i、j 同时后移)。

三、考前速览

3 句话

next[j] = 前 j−1 位最长相等前后缀 + 1。
P[j] == P[next[j]] 时 nextval 继续向前取。
KMP 主串指针不回退,O(n + m)。

3 个易错

① 看清下标从 0 还是 1 开始。
② 前缀后缀不能取整串。
③ next 只与模式串有关,与主串无关。