违法和不良信息举报 联系客服
免费注册 登录

当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。A．1222312B．1122312C．1122212D．122312

题目

当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。

A．1222312

B．1122312

C．1122212

D．122312

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

第1题：

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

A、求子串

B、联接

C、模式匹配

D、求串长


正确答案:C

第2题：

已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。


参考答案：
　　模式串t的next和nextval值如下：
　　

第3题：

设有两个串p和q，求q在p中首次出现位置的运算称作

A．连接

B．模式匹配

C．求子串

D．求串长


正确答案：B
解析：子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起和模式的第一个字符比较，若相等则继续比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。

第4题：

若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是( )。

A．O(1)

B．O(n)

C．O(n2)

D．0(n3)


正确答案：C
解析：在主串中可能存在多个模式串“部分匹配”的子串，因而引起数次回溯，若除了最后一次匹配，其他比较每次都需要回溯，则循环次数的数量级为n2。

第5题：

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

A．m

B．n-m

C．n-m+1

D．n


正确答案：C

第6题：

设目标为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)

第7题：

●在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为(57)。

(57)

A. 01111111

B.01122341

C.01234567

D.01122334


正确答案：B

第8题：

●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为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

第9题：

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


正确答案：B
试题57分析本题主要考查字符串的匹配。在本题的描述中，告诉我们是在主串末尾的m个字符处匹配成功，那么在这之前，从左到右依次匹配了n-m次，且都失败了，最坏的情况，就是每次匹配都是匹配到最后一个字符不符合，因此每次匹配的比较次数就是子串的长度，即m。而匹配成功时，一共也比较了m次。所以字符的比较次数最多为（n-m+1）*m次。参考答案（57）B

第10题：

设有两个串P和q，求q在P中首次出现的位置的运算称作______。

A．连接

B．模式匹配

C．求子串

D．求串长


正确答案：B
解析：求一个串在另一个串中首次出现的位置的运算称作模式匹配。

更多相关问题
相关内容