当前位置:首页计算机类软件水平考试中级软件设计师->模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,

模式匹配是指给定主串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)。

查看答案 纠错
答案:
本题解析:

【问题1】

(1):j<ls;

(2):t[i]==s[j];

(3):j=next[j];

(4):i-ls+1或其等价形式;

【问题2】

O(It+Is)

【问题3】

(6):[-1,-1,1,-1,-1,2,0,0],(7)6。

【问题1】

本题问题1根据KMP算法的伪代码描述进行推导。

根据伪代码中第2步可以推导(1)是判断字符串s是否还有字符,即j<ls。i表示字符串t的下标,j表示字符串s的下标。

根据伪代码第2.1步可以推导(2)是判断字符串t和字符串s当前位置的字符是否相同,即t[i]==s[j]。

根据伪代码第2.2步可以推导(3)是当第2.1步判断条件不满足时,改变j所指向的字符位置。即j=next[j]。

根据伪代码第3步可以推导(4)是返回匹配的起始位置。由于当前i所指向字符串中匹配子串的最后一个字符的位置,且已知子串的长度为ls。(4)的代码为i-ls+1或其等价形式。

【问题2】

本题问题2是计算KMP算法的复杂度。算法的复杂度一般考虑最坏情况,那么在子串读到ls及主串读到It的时候是最坏情况。所以复杂度是O(It+Is)

【问题3】

本题问题3中已知字符串“BBABBCAC”,则根据get_next()函数可以求得next数组的元素值为[-1,-1,1,-1,-1,2,0,0]。并计算得到起始位置为6。

代入字符串“BBABBCAC”到get_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];

}

}

这里涉及的只是代码的代入分析过程,注意循环的处理即可。

下面将循环过程依次代入数值并且写作顺序处理过程如下:

传参:s[]={B,B,A,B,B,C,A,C},ls=8,next[]数组只声明未取值。

初始化:i=0,j=-1,next[0]=-1。

while(i<ls)执行后面的循环体,即当i<8时执行循环。

(1)当i=0,j=-1时:

判断if(j==-1||s[0]==s[-1]),满足条件1执行下一步:i++=1,j++=0。

判断if(s[1]==s[0]),满足条件执行下一步next[1]=next[0]=-1。

【此时i=1,j=0】

(2)当i=1,j=0时:

判断if(j==-1||s[1]==s[0]),满足条件2执行下一步:i++=2,j++=1。

判断if(s[2]==s[1]),不满足条件执行else下一步next[2]=j=1。

【此时i=2,j=1】

(3)当i=2,j=1时:

判断if(j==-1||s[2]==s[1]),不满足条件1和2执行else下一步:j=next[1]=-1。

【此时i=2,j=-1】

(4)当i=2,j=-1时:

判断if(j==-1||s[2]==s[-1]),满足条件1执行下一步:i++=3,j++=0。

判断if(s[3]==s[0]),满足条件执行下一步next[3]=next[0]=-1。

【此时i=3,j=0】

(5)当i=3,j=0时:

判断if(j==-1||s[3]==s[0]),满足条件2执行下一步:i++=4,j++=1。

判断if(s[4]==s[1]),满足条件执行下一步next[4]=next[1]=-1。

【此时i=4,j=1】

(6)当i=4,j=1时:

判断if(j==-1||s[4]==s[1]),满足条件2执行下一步:i++=5,j++=2。

判断if(s[5]==s[2]),不满足条件执行else下一步next[5]=j=2。

【此时i=5,j=2】

(7)当i=5,j=2时:

判断if(j==-1||s[5]==s[2]),不满足条件1和2执行else下一步:j=next[2]=1。

【此时i=5,j=1】

(8)当i=5,j=1时:

判断if(j==-1||s[5]==s[1]),不满足条件1和2执行else下一步:j=next[1]=-1。

【此时i=5,j=-1】

(9)当i=5,j=-1时:

判断if(j==-1||s[5]==s[-1]),满足条件1执行下一步:i++=6,j++=0。

判断if(s[6]==s[0]),不满足条件执行else下一步next[6]=j=0。

【此时i=6,j=0】

(10)当i=6,j=0时:

判断if(j==-1||s[6]==s[0]),不满足条件1和2执行else下一步:j=next[0]=-1。

【此时i=6,j=-1】

(11)当i=6,j=-1时:

判断if(j==-1||s[6]==s[-1]),满足条件1执行下一步:i++=7,j++=0。

判断if(s[7]==s[0]),不满足条件执行else下一步next[7]=j=0。

【此时i=7,j=0】

(12)当i=7,j=0时:

判断if(j==-1||s[7]==s[0]),不满足条件1和2执行else下一步:j=next[0]=-1。

【此时i=7,j=-1】

(13)当i=7,j=-1时:

判断if(j==-1||s[7]==s[0]),满足条件1执行下一步:i++=8,i=ls,退出while循环。

next[]数组下标从0到7,结果分别为:[-1,-1,1,-1,-1,2,0,0]

更新时间:2021-12-10 18:17

你可能感兴趣的试题

单选题

一台主机的IP地址为202.123.25.36,掩码为255.255.254.0。如果该主机需要在该网络进行直接广播,那么它应该使用的目的地址为( )

  • A.202.123.25.0
  • B.202.123.25.255
  • C.202.123.24.0
  • D.202.123.24.255
查看答案
单选题

在计算机系统的日常维护工作中,应当注意硬盘工作时不能__(2)__。另外,需要防范病毒,而__(3)__是不会被病毒感觉的。

  • A.电子邮件
  • B.硬盘
  • C.U盘
  • D.ROM
查看答案
单选题

有 4 个 IP 地址:201.117.15.254、201.117.17.01、201.117.24.5 和 201.117.29.3,如果子网掩码为 255.255.248.0,则这 4 个地址分别属于3个子网;其中属于同一个子网的是()

  • A.201.117.15.254 和 201.117.17.01
  • B.201.117.17.01 和 201.117.24.5
  • C.201.117.15.254 和 201.117.29.3
  • D.201.117.24.5 和 201.117.29.3
查看答案
单选题

在异步通信中,每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位,每秒钟传送200个字符,采用4相位调制,则码元速率为()。

  • A.50波特
  • B.500波特
  • C.550波特
  • D.1000波特
查看答案
单选题

在 Windows 中,运行( )命令得到下图所示结果。以下关于该结果的叙述中,错误的是( )。

Pinging 59.74.111.8 with 32 bytes of data:

Reply from 59.74.111.8: bytes=32 time=3ms TTL=60

Reply from 59.74.111.8: bytes=32 time=5ms TTL=60

Reply from 59.74.111.8: bytes=32 time=3ms TTL=60

Reply from 59.74.111.8: bytes=32 time=5ms TTL=60

Ping statistics for 59.74.111.8:

Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),

Approximate round trip times in milli-seconds:

Minimum = 3ms, Maximum = 5ms, Average = 4ms

  • A.该命令使得本地主机向目标主机发送了 4 个数据包
  • B.本地主机成功收到了目标主机返回的 4 个数据包
  • C.本地主机与目标主机连接正常
  • D.该命令用于查看目标主机的 IP 地址
查看答案
单选题

在ISO OSF/RM参考模型中,七层协议中的__(1)__利用通信子网提供的服务实现两个用户进程之间端到端的通信。在这个模型中,如果A用户需要通过网络向B用户传送数据,则首先将数据送入应用层,在该层给它附加控制信息后送入表示层;在表示层对数据进行必要的变换并加头标后送入会话层;在会话层加头标送入传输层;在传输层将数据分解为__(本题)__后送至网络层;在网络层将数据封装成__(3)__后送至数据链路层;在数据链路层将数据加上头标和尾标封装成__(4)__后发送到物理层;在物理层数据以__(5)__形式发送到物理线路。B用户所在的系统接收到数据后,层层剥去控制信息,把原数据传送给B用户。

  • A.数据报
  • B.数据流
  • C.数据段
  • D.报文分组
查看答案
单选题

在OSI/RM中,解释应用数据语义的协议层是()。

  • A.数据链路层
  • B.网络层
  • C.表示层
  • D.应用层
查看答案
单选题

在TCP/IP协议栈中,ARP协议的作用是(),RARP协议的作用是(请作答此空)。

  • A.从MAC地址查找对应的IP地址
  • B.有IP地址查找对应的MAC地址
  • C.把全局IP地址转换为私网中的专用IP地址
  • D.用于动态分配IP地址
查看答案
单选题

在地址 http://www.dailynews.com.cn/channel/welcome.htm 中,www.dailynews.com.cn 表示( ),welcome.htm 表示(请作答此空)。

  • A.协议类型
  • B.主机域名
  • C.网页文件名
  • D.路径
查看答案
单选题

在电子表格软件Excel中,假设A1单元格的值为15,若在A2单元格输入“=AND(15<A1,A1<100)”,则A2单元格显示的值为 ()

  • A.TRUE
  • B.=AND(15<A1,A1<100)
  • C.FALSE
  • D.AND(15<A1,A1<100)
查看答案