目标

辨析模式匹配的定义、朴素匹配与 KMP 的指针行为与复杂度，掌握 next 与 nextval 的推导、KMP 匹配过程的比较次数统计，并用 2019/2024 统考真题与中科院 2018、西安邮电 2019 考研真题检验。

前置知识

建议先阅读 3.2 模式匹配与 KMP 正文。本套题目默认采用王道教材的 1-based 约定（next[1] = 0、nextval[1] = 0），滑动距离为 $j-nextval[j]$。教材正文采用 next[0] = -1 的 0-based 约定，两套约定对同一模式串只差一个整体平移（0-based 值 = 1-based 值 − 1），选项写法不同（如 0111232 与 -1,0,0,0,1,2,1）即标明所用约定，答案本身不受影响。

环境、输入与预期输出

• 环境：任意现代浏览器；建议准备纸笔或一份错题记录。
• 输入：本页按源文件顺序整理的 15 道选择题。
• 预期输出：一份独立作答记录，以及每道错题的错误原因和正确推理。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击“提交答案”，再核对对错、正确答案和题解；
3. 做错的题点击“重新作答”后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再展开组件生成的答案总览，避免只记答案字母。

选择题

答题进度已答 0/15正确 0

第 1 题

难度★★考点串、模式匹配、基本概念

设有两个串 $S_1$ 和 $S_2$，求 $S_2$ 在 $S_1$ 中首次出现的位置的运算称为（ ）。

请选择一个答案

A求子串

B判断是否相等

C模式匹配

D连接

第 2 题

难度★★考点串、KMP、主串指针

KMP 算法的特点是在模式匹配时，指示主串的指针（ ）。

请选择一个答案

A不会变大

B不会变小

C都有可能

D无法判断

第 3 题

难度★★考点串、模式匹配、时间复杂度

设主串的长度为 $n$，子串的长度为 $m$，则简单（朴素）模式匹配算法的时间复杂度为（ ① ），KMP 算法的时间复杂度为（ ② ）。下列组合正确的是（ ）。

请选择一个答案

A① $O(m)$；② $O(n)$

B① $O(n)$；② $O(m+n)$

C① $O(mn)$；② $O(m+n)$

D① $O(m+n)$；② $O(mn)$

第 4 题

难度★★考点串、KMP、next 数组、失配处理

在 KMP 算法中，用 next 数组存放模式串的部分匹配信息。当模式串位 $j$ 与主串位 $i$ 比较时，两个字符不相等，则 $j$ 的位移方式是（ ）。

请选择一个答案

A$j=0$

B$j=j+1$

C$j$ 不变

D$j=next[j]$

第 5 题

难度★★考点串、KMP、主串指针

在 KMP 算法中，用 next 数组存放模式串的部分匹配信息。当模式串位 $j$ 与主串位 $i$ 比较时，两个字符不相等，则 $i$ 的位移方式是（ ）。

请选择一个答案

A$i=next[i]$

B$i$ 不变

C$i=0$

D$i=i+1$

第 6 题

难度★★★考点串、KMP、比较次数

设主串 $S{=}^{\prime }aabaaab{a}^{\prime }$，模式串 $T{=}^{\prime }aaa{b}^{\prime }$，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。

请选择一个答案

A10

B9

C8

D7

第 7 题

难度★★★★考点串、KMP、nextval、比较次数

设主串 $S{=}^{\prime }aabaaab{a}^{\prime }$，模式串 $T{=}^{\prime }aaa{b}^{\prime }$，采用改进后的 KMP 算法（nextval）进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。

请选择一个答案

A9

B8

C7

D6

第 8 题

难度★★★★考点串、KMP、比较次数、统考真题

设主串 $T{=}^{\prime }abaabaabcabaab{c}^{\prime }$，模式串 $S{=}^{\prime }abaab{c}^{\prime }$，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（ ）。

请选择一个答案

A9

B10

C12

D15

第 9 题

难度★★★★考点串、KMP、nextval、滑动距离、统考真题

KMP 算法使用修正后的 next 数组进行模式匹配，模式串为 $S{=}^{\prime }aabaa{b}^{\prime }$，当主串的某个字符与 $S$ 的某个字符失配时，$S$ 向右滑动的最长距离是（ ）。

请选择一个答案

A5

B4

C3

D2

第 10 题

难度★★★考点串、KMP、匹配过程、考研真题

现有字符串 $s$ 为 'aabaabaabaac'，模式串 $t$ 为 'aabaac'，那么，采用 KMP 算法，在第（ ）次匹配时，串 $t$ 在串 $s$ 中匹配成功。（中国科学院大学 2018）

请选择一个答案

A3

B4

C6

D7

第 11 题

难度★★★考点串、KMP、next 数组、考研真题

已知模式串 $s=\text{’abcabaa’}$，则该模式串的 next 函数值序列是（ ）。

请选择一个答案

A0112123

B1011232

C0111212

D0111232

第 12 题

难度★★★考点串、KMP、next 数组

串 "ababaaababaa" 的 next 数组为（ ）。

请选择一个答案

A012345678999

B012121111212

C011234223456

D0123012322345

第 13 题

难度★★★★考点串、KMP、nextval

串 "ababaabab" 的 nextval 为（ ）。

请选择一个答案

A0,1,0,1,0,4,1,0,1

B0,1,0,1,0,1,0,1,1

C0,1,0,1,0,0,0,1,1

D0,1,0,1,0,2,1,0,1

第 14 题

难度★★考点串、模式匹配、朴素匹配

设 $S=\text{"aaaaaacaaaca"}$，$P=\text{"aaac"}$，使用 BF 算法的模式匹配过程需要执行的趟数为（ ）。

请选择一个答案

A7

B2

C3

D4

第 15 题

难度★★★★考点串、KMP、nextval

在 KMP 算法中，若模式串 $T$ 中存在 $t_j=t_k$（$k=\text{next}[j]$），且 $s_i\ne t_j$ 时，则下一次不必与 $t_k$ 进行比较，而直接和（ ）进行比较。

请选择一个答案

A$t_k$

B$t_{\text{next}[k]}$

C$t_{\text{next}[j]}$

D$t_j$

答案总览（建议完成全部题目后查看）

1. 第 1 题：C
2. 第 2 题：B
3. 第 3 题：C
4. 第 4 题：D
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：C
8. 第 8 题：B
9. 第 9 题：A
10. 第 10 题：A
11. 第 11 题：D
12. 第 12 题：C
13. 第 13 题：A
14. 第 14 题：D
15. 第 15 题：B

完成清单

• 15 道题均在展开答案前独立作答；
• 每道错题都记录了错误原因，而不只抄写正确答案；
• 能不看解析写出朴素匹配与 KMP 的复杂度结论并说明理由；
• 能独立为给定模式串求出 next 与 nextval 数组；
• 能逐步模拟 KMP 匹配过程并准确统计字符比较次数。

思考题

1. 为什么 KMP 能保证主串指针 i 只增不减？这个保证依赖模式串的什么信息？
2. nextval 相比 next 额外消除了哪一类冗余比较？它会让匹配过程跳过本来可能成功的位置吗？
3. 统计字符比较次数时，最容易漏数或多数的是哪一步？
4. 滑动距离 $j-nextval[j]$ 在什么情况下最大？能否从模式串结构一眼判断？

复盘

• 我最容易把哪个结论记反：主串指针 vs 模式串指针、朴素 vs KMP 的复杂度？
• 我是否每次都能画出匹配过程表，而不是凭感觉猜次数？
• 真题与普通题在统计比较次数时有什么必须注意的差别？