首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
28
问题
阅读下列说明和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代码,字符串“BBABBCAC”的next数组元素值为(6) (直接写元素值,之间用逗号隔开)。若主串为“AABBCBBABBCACCD”,子串为“BBABBCAC”,则函数kmp的返回值是(7)。
选项
答案
(6)-1,-1,1,一1,一1,2,0,0(7)6
解析
根据C函数get—next,得到“BBABBCAC"的next数组的值为一1,一1,1,一1,一l,
2,0,0。对主串为“AABBCBBABBCACCD”和上述模式串,得到匹配位置为6,这里需要注意的是,位置从1开始。
转载请注明原文地址:https://kaotiyun.com/show/3KDZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
SSL是一个协议独立的加密方案,在网络信息分组的应用层和传输层之间提供了安全的通道。SSL主要包括SSL修改密文协议、SSL握手协议、SSL告警协议、SSL记录协议等,其协议栈见图7-16。请根据SSL协议栈结构,将(1)~(4)处空缺的协议名称填写完整。
请说出(1)、(2)、(3)、(4)、(5)对应行的含义。(1)图6-3是Windowsxp的DNS设置窗口,请指出图6-3中配置错误之处。(2)在Windowsxp系统中,根据图6-3中的相关信息,请写出默认路由。(3)图6-
阅读以下说明,回答问题1、问题2和问题3,将解答填入对应栏内。[说明]在因特网的发展过程中,WWW(WorldWideWeb)和域名服务系统(DNS)两项技术起了重大的推动作用,在域名服务系统(DNS)出现之前,所有的因特网主机名都存储
上述配置中是否有问题?请指出并说明理由。解释配置中画线部分内容含义?
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?请说出ISDN与传统PSTN的区别。
ADSL技术可以充分利用现有铜线网络,只要在用户线路两端加装ADSL设备即可为用户提供服务。请从以下术语选择适当的编号,将图5-9所示的拓扑结构中(1)~(4)空缺处的名称填写完整。【供选择的答案】A.程控交换机B.二层交换机
请说出图9-1的拓扑结构名称与特点。请比较交换机的堆叠与级联的区别。
请说出图9-1的拓扑结构名称与特点。PC2、PC4与PCI、PC3、PC5要连网且能相互访问,需要增添什么设备?
随机试题
具有“表扬可能宠坏儿童,所以很少给予儿童表扬”典型特征的师生关系模式属于()。
弓形暗点常见于
50岁男性患者,咳嗽伴声音嘶哑3个月,右锁骨上窝触及一个肿大的淋巴结,质硬无压痛,提示该患者的诊断是
心脏骤停的复苏,下列哪项不属于建立人工有效循环的措施()
患者,女性,85岁,因休克型肺炎死亡。临床死亡的诊断标准是
下列关于按计划成本进行存货核算的说法正确的是()。
银行是经营货币信用业务的特殊企业,其通过吸收储蓄存款等形式,将分散在个人手中的闲置货币集中起来,用于向工商企业发放贷款的职能属于()职能。
进行股票分割的主要作用有()。
下列情形当然发生表见代理的是()。
Conceptually,itishardtoreconcileadefenseattorney’s(i)____toensurethatfalsetestimonyisnotknowinglyputforwardw
最新回复
(
0
)