数据结构
KMP模式匹配算法是由（）同时发现的，因此而得名。A、莫里斯B、克努特C、普拉特D、克鲁伊特
题目
KMP模式匹配算法是由（）同时发现的，因此而得名。
- A、莫里斯
- B、克努特
- C、普拉特
- D、克鲁伊特
相似问题和答案
第1题：
① p的nextval函数值为0110132。(p的next函数值为0111232)。
② 利用KMP(改进的nextval)算法，每趟匹配过程如下：
第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功) abcabaa(i=15,j=8)
第2题：
●在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为(57)。
(57)
A. 01111111
B.01122341
C.01234567
D.01122334
第3题：
在KMP算法中，已知模式串为ADABCADADA，请写出模式串的next数组值()
A.0,1,1,2,1,1,2,3,4,3
B.1,2,3,2,1,1,2,4,4,3
C.0,1,1,1,2,1,2,3,4,3
D.2,1,1,2,1,1,2,3,3,4
第4题：
第5题：
B.01122
C.01211
D.01111
第6题：
当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。
A．1222312
B．1122312
C．1122212
D．122312
解析：改进的模式匹配算法的不同之处在于，每当匹配失效时，不需要回溯主串的指针，而是复用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。算法执行时就依据模式串的next函数值实现子串的滑动。next函数定义如下：依据此函数定义即可算得next函数值序列为01122312。
第7题：
在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为 (60) 。
A.01234
B.01122
C.01211
D.01111
本题考查字符串的模式匹配运算知识。KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为l的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。对于第5个字符“a”，其在模式串中的前缀为“abaa”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。综上可得，模式串“abaac”的next函数值为01122。
第8题：
已知字符串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
第9题：
B.不会变小
C.都有可能
D.无法判断
第10题：
KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
正确答案:正确