函数实现串的模式匹配算法，请在空格处将算法补充完整。intindex_bf（sqstring*s，sqstring*t，intstart）{inti=start-1，j=0；while（ilen&&jlen）if（s->data[i]==t->data[j]）{i++；j++；}else{i=（）；j=0；}if（j>=t->len）return（）；elsereturn-1；}}/*listDelete*/

题目

函数实现串的模式匹配算法，请在空格处将算法补充完整。intindex_bf（sqstring*s，sqstring*t，intstart）{inti=start-1，j=0；while（ilen&&jlen）if（s->data[i]==t->data[j]）{i++；j++；}else{i=（）；j=0；}if（j>=t->len）return（）；elsereturn-1；}}/*listDelete*/

相似考题

1.设主串长为n，模式串长为m(m≤n)，则在匹配失败的情况下，朴素匹配算法进行的无效位移次数为(30)。A．mB．n-mC．n-m+1D．n

2.设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。A、求子串B、联接C、模式匹配D、求串长

3.设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值; ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

4.●在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中,字符的比较次数最多为(57)。(57) A. n*mB. (n-m+1)*mC. (n-m-1)*mD. (n-m)*n

更多“函数实现串的模式匹配算法，请在空格处将算法补充完整。intind”相关问题

  • 第1题：

    编写算法,实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中,插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。(说明:不得使用任何库函数)


    参考答案：本题是字符串的插入问题，要求在字符串s的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。
    　　对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。
    　　[算法描述]
    　　void insert(char *s,char *t,int pos)
    　　//将字符串t插入字符串s的第pos个位置。
    　　{int i=1,x=0; char *p=s,*q=t; //p，q分别为字符串s和t的工作指针
    　　if(pos<1) {cout<<“pos参数位置非法”<　　while(*p!=’\0’&&i　　//若pos小于串s长度，则查到pos位置时，i=pos。
    　　if(*p == '/0') { cout<　　else //查找字符串的尾
    　　while(*p!= '/0') {p++; i++;} //查到尾时，i为字符‘\0’的下标，p也指向‘\0’。
    　　while(*q!= '\0') {q++; x++; } //查找字符串t的长度x，循环结束时q指向'\0'。
    　　for(j=i;j>=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。
    　　q--; //指针q回退到串t的最后一个字符
    　　for(j=1;j<=x;j++) *p--=*q--; //将t串插入到s的pos位置上
    　　[算法讨论] 串s的结束标记('\0')也后移了，而串t的结尾标记不应插入到s中。

  • 第2题：

    ●在KMP模式匹配算法中，需要求解模式串p的next函数值，其定义如下（其中，j为模式串中字符的序号）。对于模式串“abaabaca”，其next函数值序列为(57)。

    (57)

    A. 01111111

    B.01122341

    C.01234567

    D.01122334


    正确答案：B

  • 第3题：

    ● 在字符串的模式匹配过程中，如果模式串的每个字符依次和主事中一个连续的字符序列相等，则称为匹配成功。如果不能在主串中找到与模式串相同的子串，则称为匹配失败。在布鲁特—福斯模式匹配算法（朴素的或基本的模式匹配）中，若主串和模式串的长度分别为n和m（且n远大于m），且恰好在主串末尾的m个字符处匹配成功，则在上述的模式匹配过程中，字符的比较次数最多为（57）。 A.n*m B.（n-m+1）*m C.（n-m-1）*m D.（n-m）*n


    正确答案：B
    试题57分析本题主要考查字符串的匹配。在本题的描述中，告诉我们是在主串末尾的m个字符处匹配成功，那么在这之前，从左到右依次匹配了n-m次，且都失败了，最坏的情况，就是每次匹配都是匹配到最后一个字符不符合，因此每次匹配的比较次数就是子串的长度，即m。而匹配成功时，一共也比较了m次。所以字符的比较次数最多为（n-m+1）*m次。参考答案（57）B

  • 第4题：

    在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为“abaac”，则其next函数值为 (60) 。

    A.01234

    B.01122

    C.01211

    D.01111


    正确答案：B
    本题考查字符串的模式匹配运算知识。KMP是进行字符串模式匹配运算效率较高的算法。根据对next函数的定义，模式串前两个字符的next值为0、1。对于第3个字符“a”，其在模式串中的前缀为“ab”从该子串找不出前缀和后缀相同的部分，因此，根据定义，该位置字符的next值为1。对于第4个字符“a”，其在模式串中的前缀为“aba”，该子串只有长度为l的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。对于第5个字符“a”，其在模式串中的前缀为“abaa”，该子串只有长度为1的前缀“a”和后缀“a”相同，根据定义，该位置字符的next值为2。综上可得，模式串“abaac”的next函数值为01122。

  • 第5题：

    下列是在具有头结点单向链表中删除第i个结点的算法，请在空格内填上适当的语句。
    q=q->next；p=q->next；q->next=p->next
    略

  • 第6题：

    KMP模式匹配算法的改进之处是（）。

    • A、主串指针不需要回溯
    • B、模式串的指针来回移动
    • C、主串的指针也会回到之前比较过的字符
    • D、时间复杂度可以达到O（nm）

    正确答案:A

  • 第7题：

    函数实现单链表的插入算法，请在空格处将算法补充完整。int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s;int j; p=L;j=0; while((p!=NULL)&&(jnext;j++; } if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e; (1) ; (2) ; return OK;}/*ListInsert*/


    正确答案:(1)s->next=p->next (2)p->next=s

  • 第8题：

    朴素模式匹配算法，算法运行时间为O（m*n）。


    正确答案:正确

  • 第9题：

    函数depth实现返回二叉树的高度，请在空格处将算法补充完整。intdepth（Bitree*t）{if（t==NULL）return0；else{hl=depth（t->lchild）；hr=（））；if（（））returnhl+1；elsereturnhr+1；}}


    正确答案:depth（t->rchild hl>hr

  • 第10题：

    单选题
    以下各种影像匹配方法中，可以考虑辐射畸变和几何变形的算法是（）
    A

    协方差函数测度匹配算法

    B

    相关系数测度匹配算法

    C

    铅垂线轨迹法

    D

    最小二乘法影像匹配


    正确答案： A
    解析： 暂无解析

  • 第11题：

    填空题
    函数实现串的模式匹配算法，请在空格处将算法补充完整。intindex_bf（sqstring*s，sqstring*t，intstart）{inti=start-1，j=0；while（ilen&&jlen）if（s->data[i]==t->data[j]）{i++；j++；}else{i=（）；j=0；}if（j>=t->len）return（）；elsereturn-1；}}/*listDelete*/

    正确答案： i-j+1 i-t->len+1
    解析： 暂无解析

  • 第12题：

    填空题
    函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；p=L->next;j=1; while(p&&ji) return ERROR;*e= (2) ;return OK;}

    正确答案： (1)p=p->next (2)p->data
    解析： 暂无解析

  • 第13题：

    当运用改进的模式匹配算法时，模式串P='ABAABCAC'的next函数值序列为(41)。

    A．1222312

    B．1122312

    C．1122212

    D．122312


    正确答案：B
    解析：改进的模式匹配算法的不同之处在于，每当匹配失效时，不需要回溯主串的指针，而是复用已经得到的“部分匹配”的结果，将模式串向后“滑动”尽可能远的距离，再继续进行比较。算法执行时就依据模式串的next函数值实现子串的滑动。next函数定义如下：依据此函数定义即可算得next函数值序列为01122312。

  • 第14题：

    设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )

    A．m

    B．n-m

    C．n-m+1

    D．n


    正确答案：C

  • 第15题：

    函数实现单链表的删除算法，请在空格处将算法补充完整。


    正确答案：

    (1)p->next!=NULL(2)p->next=q->next

  • 第16题：

    在字符串的KMP模式匹配算法中，需先求解模式串的next函数值，其定义如下式所示，j表示模式串中字符的序号（从1开始）。若模式串p为"abaac"，则其next函数值为 （ ） 。

    A.01234
    B.01122
    C.01211
    D.01111

    答案：B
    解析：
    根据公式依次推导即可。

  • 第17题：

    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。


    正确答案:正确

  • 第18题：

    利用带密钥的Hash函数实现数据完整性保护的方法称为MD5算法


    正确答案:错误

  • 第19题：

    函数ListDelete_sq实现顺序表删除算法，请在空格处将算法补充完整。int ListDelete_sq(Sqlist *L,int i){ int k; if(i<1||i>L->length) return ERROR;for(k=i-1;klength-1;k++) L->slist[k]= （1） ; （2） ; return OK;}


    正确答案:（1）L->slist[k+1] （2） --L->Length

  • 第20题：

    函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){ LinkList p；int j；p=L->next;j=1; while(p&&ji) return ERROR;*e= (2) ;return OK;}


    正确答案:(1)p=p->next (2)p->data

  • 第21题：

    填空题
    函数实现单链表的删除算法，请在空格处将算法补充完整。int ListDelete(LinkList L,int i,ElemType *s){ LNode *p,*q; int j; p=L;j=0; while(( （1） )&&(jnext;j++; } if(p->next==NULL||j>i-1) return ERROR; q=p->next; （2） ; *s=q->data; free(q); return OK;}/*listDelete*/

    正确答案： (1)p->next!=NULL (2)p->next=q->next
    解析： 暂无解析

  • 第22题：

    判断题
    KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
    A

    对

    B

    错


    正确答案： 错
    解析： 暂无解析

  • 第23题：

    填空题
    函数depth实现返回二叉树的高度，请在空格处将算法补充完整。intdepth（Bitree*t）{if（t==NULL）return0；else{hl=depth（t->lchild）；hr=（））；if（（））returnhl+1；elsereturnhr+1；}}

    正确答案： depth（t->rchild hl>hr
    解析： 暂无解析

相关内容