首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
39
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
根据该单位防火墙与外部网络相关的网络连接参数,请将以下命令行中(1)~(4)空缺处的内容填写完整,以完成对防火墙相应的网络接口进行地址初始化的配置。FireWall(config)#ipaddressinside(1)(2)
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
在交换机上可以配置虚拟局域网(VLAN),以下是部分配置清单。回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。>enablegconfigtEnterconfigurationcommands,oneperli
请说出(1)、(2)、(3)、(4)、(5)对应行的含义。(1)图6-3是Windowsxp的DNS设置窗口,请指出图6-3中配置错误之处。(2)在Windowsxp系统中,根据图6-3中的相关信息,请写出默认路由。(3)图6-
依据给出的可选设备进行选型,将(1)~(5)处空缺的设备名称填写在相应位置将(6)~(8)处空缺的介质填写在相应位置(所给介质可重复选择)。
阅读以下关于以快速原型模型开发网管软件系统时的项目进度管理的叙述,回答问题1至问题5。【说明】某网络程序软件开发公司承接某项网络工程的网络流量统计管理软件开发任务。在进行可行性研究时,需要估算完成项目的时间进度。由于该软件公司近年来已经为采用快速
随机试题
审方时应检查
异烟肼中毒解救时可静脉给予摄入量相等的维生素是
患者,女,43岁。近3个月来劳力后心悸,气短收入院。心脏杂音20年,查体:血压:110/70mmHg,心界扩大,心率122次/分,律不齐,S1强弱不等,脉短绌,心尖Ⅲ/6级全收缩期杂音,向腋下传导,有轻度舒张期隆隆样杂音,肺底部湿啰音。此患者最可能的诊
甲公司为增值税一般纳税人,适用的增值税税率为13%,消费税税率为10%。甲公司2×20年度发生的部分交易或事项如下:(1)1月1日,甲公司接受乙公司以一批原材料进行投资,双方签订投资合同约定该批原材料的价值为100万元,但是该批原材料在当地存在活跃市场,市
评述杜鲁门的“公平施政”。
ASEAN
下面与嵌入式处理器有关的叙述中,错误的是()。
Therearsectionofthebraindoesnotcontractwithage,andonecancontinuelivingwithoutintellectualoremotionalfacultie
LanguageContextandEnglishTeachingI.Themeaningsoflanguagecontext1.Generallyspeaking:itcanbedividedintosituati
A、Beforedinner.B、Rightafterdinner.C、Duringdinner.D、Thenextday.A女士问男士是否介意在晚饭之前讨论明天的事务,男士表示不介意。故答案选A项。
最新回复
(
0
)