4.2 串的模式匹配·习题

教材导航 · 返回本节知识

复习入口

4.2 串的模式匹配 · 4.2.1 简单的模式匹配算法 · 4.2.2 串的模式匹配算法——KMP算法 · 4.2.2.1 next数组的手算方法 · 4.2.2.2 next数组的推导公式 · 4.2.2.3 KMP算法的实现 · 4.2.3 KMP算法的进一步优化

本节共15题:选择题13题,综合应用题2题。每题答案紧接题目折叠显示。

文字转录进度:15/15题。已转录题目的题干、选项和解析可编辑;示意图按需保留。

单项选择题

单项选择题 01

原书题目P118 · 解析P119 · 目视转录

设有两个串 S1S_1 和 S2S_2,求 S2S_2 在 S1S_1 中首次出现的位置的运算称为( )。

A. 求子串

B. 判断是否相等

C. 模式匹配

D. 连接

查看答案与解析

答案:C。

求子串操作是从串 S 中截取第 ii 个字符起长度为 len 的子串,选项 A 错误。选项 B、D 明显错误。

单项选择题 02

原书题目P118 · 解析P119 · 目视转录

KMP 算法的特点是在模式匹配时,指示主串的指针( )。

A. 不会变大

B. 不会变小

C. 都有可能

D. 无法判断

查看答案与解析

答案:B。

在 KMP 算法的比较过程中,主串不会回溯,所以主串的指针不会变小。

单项选择题 03

原书题目P118 · 解析P119 · 目视转录

设主串的长度为 nn,子串的长度为 mm,则简单的模式匹配算法的时间复杂度为( ),KMP 算法的时间复杂度为( )。

A. O(m)O(m)

B. O(n)O(n)

C. O(mn)O(mn)

D. O(m+n)O(m+n)

查看答案与解析

答案:C、D。

尽管实际应用中,一般情况下简单的模式匹配算法的时间复杂度近似为 O(m+n)O(m+n),但它的理论时间复杂度还是 O(mn)O(mn)。KMP 算法的时间复杂度为 O(m+n)O(m+n)。

单项选择题 04

原书题目P118 · 解析P119 · 目视转录

在 KMP 算法中,用 next 数组存放模式串的部分匹配信息。当模式串位 jj 与主串位 ii 比较时,两个字符不相等,则 jj 的位移方式是( )。

A. j=0

B. j=j+1

C. jj 不变

D. j=next[j]

查看答案与解析

答案:D。

在 KMP 算法中,当主串中的第 ii 个字符和模式串中的第 jj 个字符不匹配时,主串的位指针 ii 不变,将主串的第 ii 个字符与模式串的第 next[j] 个字符比较,即 j=next[j]。

单项选择题 05

原书题目P118 · 解析P119 · 目视转录

在 KMP 算法中,用 next 数组存放模式串的部分匹配信息。当模式串位 jj 与主串位 ii 比较时,两个字符不相等,则 ii 的位移方式是( )。

A. i=next[i]

B. ii 不变

C. i=0

D. i=i+1

查看答案与解析

答案:B。

在 KMP 算法中,当主串中的第 ii 个字符和模式串中的第 jj 个字符失配时,主串指针 ii 不回溯。

单项选择题 06

原书题目P118 · 解析P119 · 目视转录

串 ababaaababaa 的 next 数组为( )。

A. 0,1,2,3,4,5,6,7,8,9,9

B. 0,1,2,1,2,1,1,1,1,2,1,2

C. 0,1,1,2,3,4,2,2,3,4,5,6

D. 0,1,2,3,0,1,2,3,2,2,3,4,5

查看答案与解析

答案:C。

本题采用先求串 S=ababaaababaa 的部分匹配值,再求 next 数组的方法。

  • a 的前后缀都为空,最长相等前后缀长度为 0。
  • ab 的前缀 {a}∩\{a\}\cap 后缀 {b}=∅\{b\}=\varnothing,最长相等前后缀长度为 0。
  • aba 的前缀 {a,ab}∩\{a,ab\}\cap 后缀 {a,ba}={a}\{a,ba\}=\{a\},最长相等前后缀长度为 1。
  • abab 的前缀 {a,ab,aba}∩\{a,ab,aba\}\cap 后缀 {b,ab,bab}={ab}\{b,ab,bab\}=\{ab\},最长相等前后缀长度为 2。
  • ……

依次求出的部分匹配值见下表第 3 行,将其整体右移一位,低位用 −1-1 填充,见下表第 4 行。

编号123456789101112
Sababaaababaa
PM001231123456
next(低位为 -1)-100123112345

选项中 next[1] 等于 0,所以将 next 数组整体加 1。

转录核对:A、D 选项的数字个数与串长不一致,按原书保留;正确答案 C 有 12 项。

单项选择题 07

原书题目P118 · 解析P120 · 目视转录

串 ababaaababaa 的 next 数组为( )。

A. -1,0,1,2,3,4,5,6,7,8,8,8

B. -1,0,1,0,1,0,0,0,0,1,0,1

C. -1,0,0,1,2,3,1,1,2,3,4,5

D. -1,0,1,2,-1,0,1,2,1,1,2,3

查看答案与解析

答案:C。

解析见上一题。读者也可尝试用前面介绍的手算方法。

注意,next 数组是否整体加 1 都正确,需根据题意具体分析。本题采用首项为 −1-1 的约定,结果为:

编号(从 0 起)01234567891011
Sababaaababaa
next-100123112345

单项选择题 08

原书题目P118 · 解析P120 · 目视转录

设主串 S=aabaaaba,模式串 T=aaab,采用 KMP 算法进行模式匹配,到匹配成功为止,在匹配过程中进行的单个字符间的比较次数是( )。

A. 10

B. 9

C. 8

D. 7

查看答案与解析

答案:B。

假设位序从 1 开始,手工计算出 T 的 next 数组如下。

编号1234
Taaab
next0123

采用 KMP 匹配算法时:第一趟,经过 3 次比较后,发现 S[3]≠T[3];第二趟,用 S[3] 和 T[2](next[3]=2)比较,不相等;第三趟,用 S[3] 和 T[1](next[2]=1)比较,不相等;第四趟,next[1]=0,因此开始用 S[4] 和 T[1] 比较,经过 4 次比较后,匹配成功。

主串    a a b a a a b a
第一趟  a a a b
第二趟    a a a b
第三趟      a a a b
第四趟        a a a b

总比较次数为 3+1+1+4=93+1+1+4=9。

单项选择题 09

原书题目P118 · 解析P120 · 目视转录

设主串 S=aabaaaba,模式串 T=aaab,采用改进后的 KMP 算法进行模式匹配,到匹配成功为止,在匹配过程中进行的单个字符间的比较次数是( )。

A. 9

B. 8

C. 7

D. 6

查看答案与解析

答案:C。

假设位序从 1 开始,计算出 T 的 nextval 数组如下。

编号1234
Taaab
nextval0003

采用改进的 KMP 匹配算法时:第一趟,经过 3 次比较后,发现 S[3]≠T[3];第二趟,nextval[3]=0,因此开始用 S[4] 和 T[1] 比较,经过 4 次比较后,匹配成功。

主串    a a b a a a b a
第一趟  a a a b
第二趟        a a a b

总比较次数为 3+4=73+4=7。

单项选择题 10

原书题目P118 · 解析P120 · 目视转录

KMP 算法使用 nextval 数组进行模式匹配,模式串为 S=ababaaa,当主串中的某字符与 S 中的第 6 个字符失配时,S 向右滑动的距离是( )。

A. 1

B. 2

C. 3

D. 4

查看答案与解析

答案:B。

假设位序从 0 开始,计算出 nextval 数组。当比较到 S[j] 失配时,模式串向右滑动的距离为 j-nextval[j](0≤j≤60\le j\le6)。由下表可知,当 j=5j=5 时向右滑动的距离为 5−3=25-3=2。

编号 j0123456
S[j]ababaaa
next[j]-1001231
nextval[j]-10-10-131
j-nextval[j]1133525

此外,若对 KMP 算法很熟悉,则此类题也可直接动手模拟,而不需要求 nextval 数组。与第 6 个字符匹配失败,说明前面的 ababa 匹配成功,S 可向右滑动 2 位继续尝试匹配:

主串      a b a b a ? ? ? ? ?
第一趟    a b a b a a a
第二趟        a b a b a a a

失配的主串字符不是 a,向右滑动后与模式串的 b 比较。

单项选择题 11

原书题目P118 · 解析P121 · 目视转录

【2015 统考真题】已知字符串 s 为 abaabaabacacaabaabcc,模式串 t 为 abaabc。采用 KMP 算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i=j=5,则下次开始匹配时,i 和 j 的值分别是( )。

A. i=1,j=0

B. i=5,j=0

C. i=5,j=2

D. i=6,j=2

查看答案与解析

答案:C。

由题中“失配 s[i]≠t[j] 时,i=j=5”,可知题中的主串和模式串的位序都是从 0 开始的(要注意灵活应变)。按照 next 数组生成算法,对于 t 有

编号012345
tabaabc
next-100112

发生失配时,主串指针 i 不变,子串指针 j 回退到 next[j] 位置重新比较,当 s[i]≠t[j],i=j=5,由 next 表得知 next[j]=next[5]=2(位序从 0 开始)。因此,i=5,j=2。

单项选择题 12

原书题目P119 · 解析P121 · 目视转录

【2019 统考真题】设主串 T=abaabaabcabaabc,模式串 S=abaabc,采用 KMP 算法进行模式匹配,到匹配成功为止,在匹配过程中进行的单个字符间的比较次数是( )。

A. 9

B. 10

C. 12

D. 15

查看答案与解析

答案:B。

假设位序从 0 开始,按照 next 数组生成算法,对于 S 有

编号012345
Sabaabc
next-100112

第一趟连续比较 6 次,在模式串的 5 号位和主串的 5 号位匹配失败,模式串的下一个比较位置为 next[5]。即下一次比较从模式串的 2 号位和主串的 5 号位开始,然后直到模式串的 5 号位和主串的 8 号位匹配。第二趟比较 4 次,匹配成功。单个字符的比较次数为 10 次。

单项选择题 13

原书题目P119 · 解析P121 · 目视转录

【2024 统考真题】KMP 算法使用修正后的 next 数组进行模式匹配,模式串为 S=aabaab,当主串的某个字符与 S 的某个字符失配时,S 向右滑动的最长距离是( )。

A. 5

B. 4

C. 3

D. 2

查看答案与解析

答案:A。

假设位序从 0 开始,计算出 nextval 数组。当比较到 S[j] 失配时,模式串向右滑动的距离为 j-nextval[j](0≤j≤50\le j\le5)。由下表可知,当 j=4j=4 时向右滑动的距离最长,此时距离为 5。

编号 j012345
S[j]aabaab
next[j]-101012
nextval[j]-1-11-1-11
j-nextval[j]121454

综合应用题

综合应用题 01

原书题目P119 · 解析P122 · 目视转录

在字符串模式匹配的 KMP 算法中,求模式的 next 数组值的定义如下:

next⁡[j]={0,j=1,max⁡{k∣1<k<j 且 p1⋯pk−1=pj−k+1⋯pj−1},集合不为空,1,其他情况.\operatorname{next}[j]=\begin{cases} 0,&j=1,\\ \max\{k\mid1<k<j\text{ 且 }p_1\cdots p_{k-1}=p_{j-k+1}\cdots p_{j-1}\},&\text{集合不为空},\\ 1,&\text{其他情况}. \end{cases}
  1. 当 j=1j=1 时,为什么要取 next[1]=0?
  2. 为什么要取 max⁡{k}\max\{k\},kk 最大是多少?
  3. 其他情况是什么情况,为什么取 next[j]=1?
查看答案与解析

1)当模式串的第 1 个字符与主串的当前字符比较不相等时,next[1]=0,表示模式串应右滑一位,主串当前指针后移一位,再和模式串的第 1 个字符进行比较。

2)当主串中的第 ii 个字符与模式串中的第 jj 个字符失配时,主串 ii 不回溯,则假定模式串中的第 kk 个字符与主串的第 ii 个字符比较,kk 值应满足条件 1<k<j1<k<j 且 p1⋯pk−1=pj−k+1⋯pj−1p_1\cdots p_{k-1}=p_{j-k+1}\cdots p_{j-1},即 kk 为模式串的下次比较位置。kk 值可能有多个,为了不使向右滑动丢失可能的匹配,右滑距离应该取最小,因为 j−kj-k 表示右滑的距离,所以取 max⁡{k}\max\{k\}。kk 的最大值为 j−1j-1。

3)除上面两种情况外,发生失配时,主串指针 ii 不回溯,在最坏情况下,模式串从第 1 个字符开始与主串的第 ii 个字符比较。

综合应用题 02

原书题目P119 · 解析P122 · 目视转录

设有字符串 S=aabaabaabaac,P=aabaac。

  1. 求出 P 的 next 数组。
  2. 若 S 作主串,P 作模式串,试给出 KMP 算法的匹配过程。
查看答案与解析

1)P=aabaac,按照 next 数组生成算法,对于 P 有:

① 设 next[1]=0,next[2]=1。

编号123456
Paabaac
next(初始)01

② j=3 时,k=next[j-1]=next[2]=1,观察 P[j-1](P[2])与 P[k](P[1])是否相等,P[2]=a,P[1]=a,P[2]=P[1],所以 next[j]=k+1=2。

③ j=4 时,k=next[j-1]=next[3]=2,观察 P[j-1](P[3])与 P[k](P[2])是否相等,P[3]=b,P[2]=a,P[3]≠P[2]。此时 k=next[k]=1,观察 P[3] 与 P[k](P[1])是否相等,P[3]=b,P[1]=a,P[3]≠P[1]。k=next[k]=0,因为 k=0,所以 next[j]=1。

④ j=5 时,k=next[j-1]=next[4]=1,观察 P[j-1](P[4])与 P[k](P[1])是否相等,P[4]=a,P[1]=a,P[4]=P[1],所以 next[j]=k+1=2。

⑤ j=6 时,k=next[j-1]=next[5]=2,观察 P[j-1](P[5])与 P[k](P[2])是否相等,P[5]=a,P[2]=a,P[5]=P[2],所以 next[j]=k+1=3。

最后的结果为:

编号123456
Paabaac
next012123

也可以通过求部分匹配值表的方法来求 next 数组。(原书过程中用 S 指代正在求 next 的模式串,这里统一记为 P。)

2)利用 KMP 算法的匹配过程如下。

第一趟:从主串和模式串的第 1 个字符开始比较,失配时 i=6,j=6。

第二趟:next[6]=3,主串当前位置和模式串中的第 3 个字符继续比较,失配时 i=9,j=6。

第三趟:next[6]=3,主串当前位置和模式串中的第 3 个字符继续比较,匹配成功。

主串    a a b a a b a a b a a c
第一趟  a a b a a c
第二趟        a a b a a c
第三趟              a a b a a c

匹配起始位置为 7(从 1 开始计数)。