工学

单选题设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。A O（m）B O（n）C O（m*n）D O（nlog2m）

题目
单选题
设串长为n，模式串长为m，则KMP算法所需的附加空间为（）。
A

O（m）

B

O（n）

C

O（m*n）

D

O（nlog2m）

如果没有搜索结果，请直接 联系老师 获取答案。
如果没有搜索结果，请直接 联系老师 获取答案。
相似问题和答案

第1题：

设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。

A．m

B．n-m

C．n-m+1

D．n


正确答案：C
解析：本题考查字符串的匹配内容。字符串是由某字符集上的字符所组成的任何有限字符序列。字符串的匹配实际上就是在一个字符串中查找另一个字符串，如果查找到则说明匹配成功。在一个字符串中查找另一个字符串时，是从主串的第一个字符开始的，用其第一个字符与模式串中的第一个字符比较，看是否相等，如果不等则主串往后移动一位，如果查找不到，那么只需要把主串移动到n-m+1位置即可，因为后面就算再出现能查找到的情况那也没有模式串的长度了，肯定不能完全查找出模式串。那么在匹配过程中，进行的无效位移次数为n-m+1次。

第2题：

●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。

(57) A. n*m

B. (n-m+1)*m

C. (n-m-1)*m

D. (n-m)*n


正确答案：B

第3题：

设串的长度为n,则它的子串个数为()。

A、n

B、n(n+1)

C、n(n+1)/2

D、n(n+1)/2+1


参考答案：C

第4题：

已知串S=’aaabaaacdadd’(注意d和add之间有一个空格),则串长为()。

A、14

B、13

C、12


参考答案：B

第5题：

设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。

A、求子串

B、联接

C、模式匹配

D、求串长


正确答案:C

第6题：

在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


正确答案：A

第7题：

已知字符串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

第8题：

设串S的长度为n,则S的子串个数为n(n＋1)／2。()

此题为判断题(对，错)。


参考答案：错误

第9题：

设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值; ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。


参考答案：
　　① 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)

第10题：

设串s="I AM A STUDENT",则其串长是()。

A.13

B.14

C.15

D.16


参考答案：B

更多相关问题
相关内容