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 · 目视转录
设有两个串 和 ,求 在 中首次出现的位置的运算称为( )。
A. 求子串
B. 判断是否相等
C. 模式匹配
D. 连接
查看答案与解析
答案:C。
求子串操作是从串 S 中截取第 个字符起长度为 len 的子串,选项 A 错误。选项 B、D 明显错误。
单项选择题 02
原书题目P118 · 解析P119 · 目视转录
KMP 算法的特点是在模式匹配时,指示主串的指针( )。
A. 不会变大
B. 不会变小
C. 都有可能
D. 无法判断
查看答案与解析
答案:B。
在 KMP 算法的比较过程中,主串不会回溯,所以主串的指针不会变小。
单项选择题 03
原书题目P118 · 解析P119 · 目视转录
设主串的长度为 ,子串的长度为 ,则简单的模式匹配算法的时间复杂度为( ),KMP 算法的时间复杂度为( )。
A.
B.
C.
D.
查看答案与解析
答案:C、D。
尽管实际应用中,一般情况下简单的模式匹配算法的时间复杂度近似为 ,但它的理论时间复杂度还是 。KMP 算法的时间复杂度为 。
单项选择题 04
原书题目P118 · 解析P119 · 目视转录
在 KMP 算法中,用 next 数组存放模式串的部分匹配信息。当模式串位 与主串位 比较时,两个字符不相等,则 的位移方式是( )。
A. j=0
B. j=j+1
C. 不变
D. j=next[j]
查看答案与解析
答案:D。
在 KMP 算法中,当主串中的第 个字符和模式串中的第 个字符不匹配时,主串的位指针 不变,将主串的第 个字符与模式串的第 next[j] 个字符比较,即 j=next[j]。
单项选择题 05
原书题目P118 · 解析P119 · 目视转录
在 KMP 算法中,用 next 数组存放模式串的部分匹配信息。当模式串位 与主串位 比较时,两个字符不相等,则 的位移方式是( )。
A. i=next[i]
B. 不变
C. i=0
D. i=i+1
查看答案与解析
答案:B。
在 KMP 算法中,当主串中的第 个字符和模式串中的第 个字符失配时,主串指针 不回溯。
单项选择题 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的前缀 后缀 ,最长相等前后缀长度为 0。aba的前缀 后缀 ,最长相等前后缀长度为 1。abab的前缀 后缀 ,最长相等前后缀长度为 2。- ……
依次求出的部分匹配值见下表第 3 行,将其整体右移一位,低位用 填充,见下表第 4 行。
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| PM | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| next(低位为 -1) | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
选项中 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 都正确,需根据题意具体分析。本题采用首项为 的约定,结果为:
| 编号(从 0 起) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| S | a | b | a | b | a | a | a | b | a | b | a | a |
| next | -1 | 0 | 0 | 1 | 2 | 3 | 1 | 1 | 2 | 3 | 4 | 5 |
单项选择题 08
原书题目P118 · 解析P120 · 目视转录
设主串 S=aabaaaba,模式串 T=aaab,采用 KMP 算法进行模式匹配,到匹配成功为止,在匹配过程中进行的单个字符间的比较次数是( )。
A. 10
B. 9
C. 8
D. 7
查看答案与解析
答案:B。
假设位序从 1 开始,手工计算出 T 的 next 数组如下。
| 编号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| T | a | a | a | b |
| next | 0 | 1 | 2 | 3 |
采用 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
总比较次数为 。
单项选择题 09
原书题目P118 · 解析P120 · 目视转录
设主串 S=aabaaaba,模式串 T=aaab,采用改进后的 KMP 算法进行模式匹配,到匹配成功为止,在匹配过程中进行的单个字符间的比较次数是( )。
A. 9
B. 8
C. 7
D. 6
查看答案与解析
答案:C。
假设位序从 1 开始,计算出 T 的 nextval 数组如下。
| 编号 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| T | a | a | a | b |
| nextval | 0 | 0 | 0 | 3 |
采用改进的 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
总比较次数为 。
单项选择题 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]()。由下表可知,当 时向右滑动的距离为 。
| 编号 j | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| S[j] | a | b | a | b | a | a | a |
| next[j] | -1 | 0 | 0 | 1 | 2 | 3 | 1 |
| nextval[j] | -1 | 0 | -1 | 0 | -1 | 3 | 1 |
| j-nextval[j] | 1 | 1 | 3 | 3 | 5 | 2 | 5 |
此外,若对 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 有
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| t | a | b | a | a | b | c |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
发生失配时,主串指针 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 有
| 编号 | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| S | a | b | a | a | b | c |
| next | -1 | 0 | 0 | 1 | 1 | 2 |
第一趟连续比较 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]()。由下表可知,当 时向右滑动的距离最长,此时距离为 5。
| 编号 j | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| S[j] | a | a | b | a | a | b |
| next[j] | -1 | 0 | 1 | 0 | 1 | 2 |
| nextval[j] | -1 | -1 | 1 | -1 | -1 | 1 |
| j-nextval[j] | 1 | 2 | 1 | 4 | 5 | 4 |
综合应用题
综合应用题 01
原书题目P119 · 解析P122 · 目视转录
在字符串模式匹配的 KMP 算法中,求模式的 next 数组值的定义如下:
- 当 时,为什么要取 next[1]=0?
- 为什么要取 , 最大是多少?
- 其他情况是什么情况,为什么取 next[j]=1?
查看答案与解析
1)当模式串的第 1 个字符与主串的当前字符比较不相等时,next[1]=0,表示模式串应右滑一位,主串当前指针后移一位,再和模式串的第 1 个字符进行比较。
2)当主串中的第 个字符与模式串中的第 个字符失配时,主串 不回溯,则假定模式串中的第 个字符与主串的第 个字符比较, 值应满足条件 且 ,即 为模式串的下次比较位置。 值可能有多个,为了不使向右滑动丢失可能的匹配,右滑距离应该取最小,因为 表示右滑的距离,所以取 。 的最大值为 。
3)除上面两种情况外,发生失配时,主串指针 不回溯,在最坏情况下,模式串从第 1 个字符开始与主串的第 个字符比较。
综合应用题 02
原书题目P119 · 解析P122 · 目视转录
设有字符串 S=aabaabaabaac,P=aabaac。
- 求出 P 的 next 数组。
- 若 S 作主串,P 作模式串,试给出 KMP 算法的匹配过程。
查看答案与解析
1)P=aabaac,按照 next 数组生成算法,对于 P 有:
① 设 next[1]=0,next[2]=1。
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| P | a | a | b | a | a | c |
| next(初始) | 0 | 1 |
② 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。
最后的结果为:
| 编号 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| P | a | a | b | a | a | c |
| next | 0 | 1 | 2 | 1 | 2 | 3 |
也可以通过求部分匹配值表的方法来求 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 开始计数)。