问题详情
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。如果匹配成功,返回s在t中的位置,否则返回-1 。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下: 1.在串t和串s中,分别设比较的起始下标i=j=0。 2.如果串t和串s都还有字符,则循环执行下列操作:(1)如果j=-l或者t[i]=s[j],则将i和j分别加1,继续比较t和s的下一个字符;(2)否则,将j向右滑动到next[j]的位置,即j =next[j]。 3.如果s中所有字符均已比较完毕,则返回匹配的起始位置(从1开始);否则返回-1.其中,next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】
(1)常量和变量说明
t,s:长度为悯铂Is的字符串
next:next数组,长度为Is
(2)C程序
#include
#include
#include
/*求next[]的值*/
void get_next( int *next, char *s, int Is)
{
int i=0,j=-1;
next[0]=-1;/*初始化next[0]*/
while(i < ls){/*还有字符*/
if(j==-1l
ls[i]==s[j]){/*匹配*/
j++;
i++;
if( s[i]==s[j])
next[i]
= next[j];
else
Next[i]
= j;
}
else
j = next[j];
}
}
int kmp( int *next, char *t ,char *s, int
lt, int Is )
{
Int i=
0,j =0 ;
while
(i < lt &&(1) ){
if(
j==-1 || (2)){
i
++ ;
j
++ ;
}
else
(3);
}
if (j >= ls)
return (4) ;
else
return -1;
} 【问题1】(8分)
根据题干说明,填充C代码中的空(1)~(4).
【问题2】(2分)
根据题干说明和C代码,分析出kmp算法的时间复杂度为(5)(主串和子串的长度分别为It和Is,用O符号表示)。
【问题3】(5分)
根据C代码,字符串“BBABBCAC”的next数组元素值为(6)(直接写素值,之间用逗号隔开)。若主串为“AABBCBBABBCACCD”,子串为“BBABBCAC”,则函数Kmp的返回值是(7)。
未搜索到的试题可在搜索页快速提交,您可在会员中心"提交的题"快速查看答案。
收藏该题
查看答案
搜题
相关问题推荐
开-闭原则(Open-Closed Principle,OCP)是面向对象的可复用设计的基石。开-闭原则是指一个软件实体应当对( )开放,对( )关闭;里氏代换原则(Liskov Substitution Principle,LSP)是指任何( )可以出现的地方,(请作答此空)一定可以出现。依赖倒转原则(Dependence Inversion Principle,DIP)就是要依赖于( )而不依赖于( ),或者说要针对接口编程,不要针对实现编程。
A.变量
B.常量
C.基类对象
D.子类对象
A.变量
B.常量
C.基类对象
D.子类对象
黑盒测试不能发现______。
A.功能错误或者遗漏
B.输入输出错误
C.执行不到的代码
D.初始化和终止错误
A.功能错误或者遗漏
B.输入输出错误
C.执行不到的代码
D.初始化和终止错误
三总线结构的计算机总线系统由()组成。
A.CPU总线、内存总线和IO总线
B.数据总线、地址总线和控制总线
C.系统总线、内部总线和外部总线
D.串行总线、并行总线和PCI总线
A.CPU总线、内存总线和IO总线
B.数据总线、地址总线和控制总线
C.系统总线、内部总线和外部总线
D.串行总线、并行总线和PCI总线
以下关于极限编程XP的叙述中,不正确的是()。
A.由价值观,原则,实践和行为四个部分组成
B.每个不同的项目都需要一套不同的策略,约定和方法论
C.有四个价值观,即沟通,简单性,反馈和勇气
D.有五大原则,即快速反馈,简单性假设,逐步修改,提倡更改和优质工作
A.由价值观,原则,实践和行为四个部分组成
B.每个不同的项目都需要一套不同的策略,约定和方法论
C.有四个价值观,即沟通,简单性,反馈和勇气
D.有五大原则,即快速反馈,简单性假设,逐步修改,提倡更改和优质工作
将某高级语言程序翻译为汇编语言形式的目标程序,该过程称为()。
A.编译
B.解释
C.汇编
D.解析
A.编译
B.解释
C.汇编
D.解析