首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。如果匹配成功,返回s在t中的位置,否则返回一1。 KMP算法用next数组对匹配过程进行了优化。K
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。如果匹配成功,返回s在t中的位置,否则返回一1。 KMP算法用next数组对匹配过程进行了优化。K
admin
2017-11-28
38
问题
阅读下列说明和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=1或者t
=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:长度为1t和1s的字符串
next:next数组,长度为1s
(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
if(j==一1‖s
=s[j]){/*匹配*/
j++
i++;
if(s
==s[j])
next
=next[j];
else
next
=j;
}
else
j=next[j];
}
}
int kmp(int*next,Char*t,char*s,int it,int is)
{
int i=0,j=0;
while(i
if(j=一1 ‖ (2) ){
i ++;
j++;
} else
(3) ,
}
if ( j>=ls)
return (4);
else
return一1;
}
根据题干说明和C代码,分析出KMP算法的时间复杂度为(5) (主串和子串的长度分别为1t和1s,用O符号表示)。
选项
答案
(5)O(1t+1s)
解析
在kmp函数中,只有一个while循环,该算法的时间复杂度为O(1t+1s)。
转载请注明原文地址:https://kaotiyun.com/show/tKDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
阅读以下关于交换机VTP协议配置的技术说明,根据要求回答问题1至问题4。【说明】利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。利用showvtpstatus命令在某台交换机的特权模式
阅读以下关于某硬件防火墙相关配置的技术说明,根据要求回答问题1至问题4。【说明】某单位在部署内部局域网时选用了一款硬件防火墙,该防火墙分别带有“WAN”、“LAN”“DMZ”、“FUN”等4个网络接口,支持Web界面、命令行等多种管理模式。该单位
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
请说出(1)、(2)、(3)、(4)、(5)对应行的含义。(1)图6-3是Windowsxp的DNS设置窗口,请指出图6-3中配置错误之处。(2)在Windowsxp系统中,根据图6-3中的相关信息,请写出默认路由。(3)图6-
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出ISDN与传统PSTN的区别。
将图2-2中(1)和(2)空缺名称填写在对应的解答栏内。按照G.lite的最高速率标准,上传24MB的文件需要多少秒时间?
随机试题
【背景资料】某施工单位承建某铁路客运专线双线隧道。隧道长度为2600m,起止里程为DK38+000~DK40+600。进、出口段浅埋,围岩为风化泥灰岩,岩体破碎,节理发育,裂隙水丰富,级别为Ⅴ级;洞身DK39+100~DK39+500段围岩级级为
某小区五楼刘某家的抽油烟机发生故障,王某与李某上门检测后,决定拆下搬回维修站修理。刘某同意。王某与李某搬运抽油烟机至四楼时,王某发现其中藏有一包金饰,遂暗自将之塞入衣兜。(事实一)王某与李某将抽油烟机机搬走后,刘某想起自己此前曾将金饰藏于其中,追赶前来,
处理肉芽过度增生的药物是
与可摘局部义齿稳定无关的是
A.曲泽B.间使C.内关D.大陵E.劳宫可用于治疗鹅掌风的穴位是
尿少,口干,皮肤弹性稍差,血压为11.3/7.7kPa,呼吸深快,口唇樱红,前囟门凹陷,心音低钝,肺无啰音,腹胀,四肢无力、稍凉,血钠132mmol/L。可能的诊断是
患儿,女,3岁,因发热3日伴流涕、咳嗽、流泪来诊。护士预诊时发现该患儿体温39.4℃,结膜充血、畏光流泪,并且在颊黏膜上出现柯氏斑,应首先考虑的疾病是()
甲公司是一家软件企业,80%的员工都是资深的程序员,则该企业适合于采用()。
心理咨询最终的目标是()。
Youwillhearanotherfiverecordings.Eachspeakerrecentlyattendedaninterview.Foreachrecording,decidewhatthespea
最新回复
(
0
)