首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
42
问题
阅读下列说明和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头
认真阅读以下关于架构Apache安全服务器的技术说明,根据要求回答问题1至问题5。【说明】某些商务公司要求其网站的部分信息资源只对经过身份认证后的用户开放。因此在Linux+Apache架构Web服务器方案中,需利用mod-ss1模块给Apach
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
如果在网络设计过程中划分了很多VLAN,则可采用VTP来简化其管理。交换机管理IP地址只能创建在(1)中,而VTP信息只能在(2)端口上传播。共享相同VLAN数据库的交换机构成一个(3)。不同交换机平台、不同的IOS版本支持的VLAN数量不同,从图6-18
根据该单位防火墙与外部网络相关的网络连接参数,请将以下命令行中(1)~(4)空缺处的内容填写完整,以完成对防火墙相应的网络接口进行地址初始化的配置。FireWall(config)#ipaddressinside(1)(2)
阅读以下关于ADSL宽带接入Internet的技术说明,请结合网络拓扑结构图,根据要求回答问题1至问题5。【说明】某边远山区的行政机关需要与该地区的市委行政机关进行网络互连,提高行政办事效率,并要求与Internet网互连,从而打开该山区原信息
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。某商务公司在全国各城市共有15个分支机构,这些机构已经建设了基于大型关系数据库的信息管理系统,每天负责独立地处理本区域内的业务并实时存储业务数据。每个
请用100字以内的文字说明该网管软件项目采用快速原型开发方法的优缺点。项目管理就是以项目为对象的系统管理方法,通过一个临时性的专门的柔性组织,对项目进行高效率的计划、组织、指导和控制,以实现项目全过程的动态管理和项目目标的综合协调与优化。除了本题涉及到
阅读以下关于以快速原型模型开发网管软件系统时的项目进度管理的叙述,回答问题1至问题5。【说明】某网络程序软件开发公司承接某项网络工程的网络流量统计管理软件开发任务。在进行可行性研究时,需要估算完成项目的时间进度。由于该软件公司近年来已经为采用快速
随机试题
患者,女性,39岁。持续高热1周,体温持续在39.0~40.2℃,以发热待查,于上午8时收入院。入院时测体温40℃,脉搏118次/分,呼吸28次/分,血压120/80mmHg,神志清楚,面色潮红,口唇干裂,食欲不振。上午8:20给予退热剂后,体温降至38.
简述处理与顾客公众关系的艺术。
不属于非霍奇金淋巴瘤病理学分型的是
IgM
如图所示,一重为G的重物静止在斜面上,摩擦角为φmax。其顶部由铅垂方向的绳子拉住,则重物受到斜面约束力的方向以及θ与φmax的关系是()。
生态影响评价的分级根据评价项目(),将生态影响评价工作级别划分为1、2、3级。
【背景资料】某施工单位承建了某双线五跨变截面预应力混凝土连续刚构梁桥,桥长612m,跨径布置为81m+3×150m+81m。主桥基础均采用钻孔灌注桩,主墩墩身为薄壁单室空心墩,墩身最大高度60m,主桥0号、1号块采用单箱单室结构,顶板宽12m,翼板宽3m
最高人民检察院对()负责。
一个教师可讲授多门课程,一门课程可由多个教师讲授,则实体教师和课程间的联系是()。
A、Hewondersifhe’llhaveenoughtimetodothejob.B、Heisafraidhewon’tknowenoughtodothejobwell.C、Hefearsthatth
最新回复
(
0
)