主观题

模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。如果匹配成功,返回s在t中的位置,否则返回-1。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下:
1.在串t和串s中,分别设比较的起始下标i=j=0。
2.如果串t和串s都还有字符,则循环执行下列操作:
(1)如果j=-l或者t[i]=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:长度为lt和Is的字符串
next:next数组,长度为ls
(2)C程序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*求next[]的值*/
void get_next(int*next,char*s,int ls){
int i=0,j=-1;
next[0]=-1;/*初始化next[0]*/
while(i<ls){/*还有字符*/
if(j==-1l ls[i]==s[j]){/*匹配*/
j++;
i++;
if(s[i]==s[j])
next[i]=next[j];
else
Next[i]=j;
}
else
j=next[j];
}
}
int kmp(int*next,char*t,char*s,int lt,int Is)
{
Int i=0,j=0;
while(i<lt&&(1)){
if(j==-1||(2)){
i++;
j++;
}else
(3);
}
if(j>=ls)
return(4);
else
return-1;
}
【问题1】(8分)
根据题干说明,填充C代码中的空(1)~(4).
【问题2】(2分)
根据题干说明和C代码,分析出kmp算法的时间复杂度为(5)(主串和子串的长度分别为lt和ls,用O符号表示)。
【问题3】(5分)
根据C代码,字符串“BBABBCAC”的next数组元素值为(6)(直接写素值,之间用逗号隔开)。若主串为“AABBCBBABBCACCD”,子串为“BBABBCAC”,则函数Kmp的返回值是(7)。

查看答案
该试题由用户339****73提供 查看答案人数:45546 如遇到问题请 联系客服
正确答案
该试题由用户339****73提供 查看答案人数:45547 如遇到问题请联系客服

相关试题

换一换
单选题
应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配,在匹配成功时,进行的字符比较总次数为()
A.A.7 B.B.9 C.C.10 D.D.12
答案
单选题
应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配,在匹配成功时,进行的字符比较总次数为()
答案
判断题
通常将子串在主串中首次出现时,该子串首字符对应的主串中的序号,定义为子串在主串中的位置
答案
主观题
设有两个串S和T,其中T是S的子串,求T在S中首次出现的位置的算法称为
答案
判断题
串 s 是 s 本身的真子串。( )
答案
判断题
任意串s都是s本身的子串
答案
主观题
设目标串为s,模式串为是t,在KMP模式匹配中,next[4]=2的含义是
答案
单选题
已知字符串s="(X+Y)+Z",其中,单引号不是字符串的内容,经过以下运算后,t3的值是( )。t1=SubString(s,3,1)t2=Concat("XY",t 1)t3=Replace(s,SubString(s,1,5),t2)注:SubString(s,k,n)表示从串s的第k个字符开始取出长度为n的子串,Concat(s,t)表示将串t连接在s之后,Replace(s,t,r)表示用r替换串s中的子串t。
A."XY+Z*" B."(X+Z)*Y" C."XYZ+*" D."XY+*Z"
答案
单选题
己知字符串 s="(X+Y)*Z" ,其中,单引号不是字符串的内容, 经过以下运算后,t3 的值是( )。t1=SubString(s ,3,1)t2=Concat("XY" ,t1)t3=Replace(s,SubString(s,1,5),t2)注: SubString(s,k,n)表示从串 s的第 k 个字符开始取出长度为 n 的子串, Concat(s,t)表示将串 t 连接在 s 之后, Replace(s,t,r)表示用 r 替换串 s 中的子串 t。
A.;XY Z*’ B."(X Z)*Y" C."XYZ *’ D."XY+*Z’
答案
判断题
除 s 本身之外,s 的其它子串称为 s 的真子串。( )
答案
热门试题
若串S="software",其子串(含串)的个数是 在串的模式匹配运算中,被匹配的主串称为模式。 子串的定位运算称为串的模式匹配() 阅读以下说明和C函数,将解答填入答题纸的对应栏内。
【说明】
函数del_substr(S,T)的功能是从头至尾扫描字符串S,删除其中与字符串T相同的所有子串,其处理过程为:首先从串S的第一个字符开始查找子串T,若找到,则将后面的字符向前移动将子串T覆盖掉,然后继续查找子串T,否则从串S的第二个字符开始查找,依此类推,重复该过程,直到串S的结尾为止。该函数中字符串的存储类型SString定义如下:
typedef struct{
char *ch; /*串空间的首地址*/
int length; /*串长*/
}SString;

【C函数】
void del substr(SString*S, SString T)

int i, j;
if(S->length<1||T.length<1||S->length<T.length)
return;
i=0; /* i为串S中字符的下标 */
for(;;){
j=0; /* j为串T中字符的下标 */
while(i<S->length&&j<T.length){ /* 在串S中查找与T相同的子串 */
if(S->ch[i]==T.ch[j]){
i++; j++;
}
else{
i= (1) ; j=0; /* i值回退,为继续查找T做准备 */


if( (2) ){ /* 在S中找到与T相同的子串 */
i= (3) ; /* 计算S中子串T的起始下标 */
for(k=i+T.length; k<S->length; k++) /* 通过覆盖子串T进行删除 */
S->ch[ (4) ]=S->ch[k];
S->length= (5) ; /* 更新S的长度*/

else break; /* 串S中不存在子串T */

若串S=“master”其子串的个数是( )。 若串S=”software”,其子串的个数是() 若串S=”myself”,其子串的数目是__ 设有字符串 S 和 P,串的模式匹配是指( )。 子串“ABC”在主串“AABCABCD”中的位置为2。(? ) 设主串为“FABcCDABcdEFaBc”,以下模式串能与主串成功匹配的是()。 若串S=’computer’,其真子串的数目是( )。 设有字符串S和P,串的模式匹配是指确定( )。 设有字符串S和P,串的模式匹配是指确定( )。 若串s="Program",则其子串的数目是 【3】 。 若串s="Program",则其子串的数目是 【1】 。 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串,函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”,则调用函数Scopy(P,Sub(S,1,7))后得到()。 若串S=“software”,则其子串数目是____,其中空串和S串本身这两个字符串也算作S的字串 串s=″DataStructure″中长度为3的子串的数目是() 串s=″DataStructure″中长度为3的子串的数目是() 在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特—福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式串的长度分别为n和m(且n远大于m),且恰好在主串末尾的m个字符处匹配成功,则在上述的模式匹配过程中,字符的比较次数最多为(  )。
购买搜题卡 会员须知 | 联系客服
会员须知 | 联系客服
关注公众号,回复验证码
享30次免费查看答案
微信扫码关注 立即领取
恭喜获得奖励,快去免费查看答案吧~
去查看答案
全站题库适用,可用于E考试网网站及系列App

    只用于搜题看答案,不支持试卷、题库练习 ,下载APP还可体验拍照搜题和语音搜索

    支付方式

     

     

     
    首次登录享
    免费查看答案20
    微信扫码登录 账号登录 短信登录
    使用微信扫一扫登录
    登录成功
    首次登录已为您完成账号注册,
    可在【个人中心】修改密码或在登录时选择忘记密码
    账号登录默认密码:手机号后六位