🏷️ 知识点：串的模式匹配

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

A. 求子串 D. 连接

[tag_link]

正确答案：C

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

A. 不会变大 B. 不会变小 C. 都有可能 D. 无法判断

[tag_link]

正确答案：B

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

A. O(m) B.O(n) C.O( mn) D.O(m + n)

[tag_link]

正确答案：

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

A. j=0 B.j=j+1 C. j 不变 D. j =next[j]

[tag_link]

正确答案：D

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

A. i=next[i] B. i 不变 C.i=0 D.i=i+1

[tag_link]

正确答案：B

串 ‘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

[tag_link]

正确答案：C

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

A. 10 B.9 C. 8 D.7

[tag_link]

正确答案：B

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

A. 9 B.8 C. 7 D.6

[tag_link]

正确答案：C

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

A. 1 B.2 C.3 D.4

[tag_link]

正确答案：B

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

A. 5 B.4 C. 3 D. 2

[tag_link]

正确答案：A

在字符串模式匹配的 KMP 算法中，求模式的next 数组值的定义如下： 集合不为空 1 ) 当j=1 时，为什么要取next[1]=0? 2)为什么要取max{k},k 最大是多少? 3)其他情况是什么情况，为什么取next[j]=1?

[tag_link]

C

设有字符串 S=‘a abaabaabaac ‘,P=’ aabaac’。 1)求出P 的 next 数组。 2 ) 若S 作为主串，P 作为模式串，试给出KMP 算法的匹配过程。

[tag_link]

B