首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读下列说明和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
29
问题
阅读下列说明和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
软件设计师下午应用技术考试
软考中级
相关试题推荐
简述网络规划阶段需求分析的方法和解决的问题。(控制在100个字以内)在网络规划阶段“系统可行性分析和论证”的主要内容是什么?(控制在100个字以内)
从工作的频段、数据传输速率、优缺点以及它们之间的兼容性等方面,对IEEE802.11a、IEEE802.11b和IEEE802.11g进行比较。简述WLAN用户通过RADIUS服务器登录的过程。
在Internet上捕获并分析图8-16所示的网络中两个内部网络经由Internet通信的L2TPv2数据帧,请从以下4个选项中选择正确的答案填写到图8-17的(1)~(4)空缺处的相应位置。【供选择的答案】A.L2TPv2头
PGP协议采用RSA和IDEA两种加密算法组成链式加密体系,这种方案的优点是(1)。PGP还可以对电子邮件进行认证,认证机制是用MD5算法产生(2)位的报文摘要,发送方用自己的RSA私钥对(3)进行加密,附加在邮件中进行传送。公钥只用来加密(4),文件是用
阅读以下关于交换机VTP协议配置的技术说明,根据要求回答问题1至问题4。【说明】利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。利用showvtpstatus命令在某台交换机的特权模式
非对称数字用户线(AsymmetricDigitalSubscriberLine,ADSL)是一种利用现有的传统电话线路高速传输数字信息的技术。ADSL技术可以充分利用现有铜线网路,只要在用户线路两端加装ADSL设备即可为用户提供服务。ADSL系统构
阅读以下关于ADSL宽带接入Internet的技术说明,请结合网络拓扑结构图,根据要求回答问题1至问题5。【说明】某边远山区的行政机关需要与该地区的市委行政机关进行网络互连,提高行政办事效率,并要求与Internet网互连,从而打开该山区原信息
阅读以下说明,回答问题1和问题2。【说明】某学校拟组建一个小型校园网,具体设计如下:1.设计要求。(1)终端用户包括:48个校园网普通用户;一个有24个多媒体用户的电子阅览室;一个有48个用户的多媒体教室(性能要求高于电子阅
阅读以下说明,回答【问题1】~【问题4】,将解答填入空白处。【说明】某小型单位的网络图如图5所示,Cisco路由器有ISDN模块,单位通过ISDN连接Internet。ISDN是指近年来供最终用户使用的一套数字服务,包括电话网络的数字化,以便ISP
阅读以下关于网络应用系统可靠性分析方面的技术说明,根据要求回答问题1至问题4。【说明】可靠性是一个网络应用系统能正常工作的能力,一般用平均故障间隔时间(MTBF)来度量。某网络应用软件研发公司正在开发一个嵌入式实时应用软件——宽带路由器的NanO
随机试题
在不同实验室由不同分析人员测定结果的精密度称为
四环素类抗药作用的机制是
提供互联网药品信息服务的网站可以发布产品信息的药品包括()
由于建筑产品采取( )的承发包生产,因此,其质量目标的决策是建设单位(业主)或项目法人的质量职能,尽管建设项目的前期工作,业主可以采用社会化、专业化的方式,委托咨询机构、设计单位或建设工程总承包企业进行,但这一切并不改变业主或项目法人的决策性质。
发行人应披露( )制度的建立健全及运行情况,说明上述机构和人员履行职责的情况。
对于《美化生活的装饰》这堂课,下列三维目标的表述不正确的是()。
中学教学的一般任务有()。
《刑法》第313条规定:“对人民法院的判决、裁定有能力执行而拒不执行,情节严重的,处三年以下有期徒刑、拘役或者罚金;情节特别严重的,处三年以上七年以下有期徒刑,并处罚金。单位犯前款罪的,对单位判处罚金,并对其直接负责的主管人员和其他直接责任人员,
与十六进制数CD等值的十进制数是——。
A、Fullcoveragerestrictstheamountusedoncardamages.B、Fullcoverageonlycoversthedamagesofsomeoneelse’scar.C、Full
最新回复
(
0
)