模式匹配是指给定主串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]
包含此试题的试卷
你可能感兴趣的试题
Advancements in （ ）have contributed to the growth of the automotive industry through the creation and evolution of self-driving vehicles.
-
- A.Artificial Intelligence
- B.Cloud Computing
- C.Internet of Things
- D.Big Data
- 查看答案
In project human resource management , （ ）is not a source of power for the project manager.
-
- A.referent power
- B.expert power
- C.reward power
- D.audit power
- 查看答案
At the project establishment stage , the feasibility study mainly includes techinical feasibility analysis , （ ）, operation environment feasibility analysis and other aspects of feasibility analysis.
-
- A.detail feasibility analysis
- B.opportunity analysis
- C.economic feasibility analysis
- D.risk analysis
- 查看答案
（ ）is a grid that shows the project resources assigned to each work package.
-
- A.Stakeholder engagement assessment matrix
- B.Requirements traceability matrix
- C.Probability and impact matrix
- D.Responsibility assignment matrix
- 查看答案
Xinhua News Agency reported in January 2022，Chian will further promote the developmet of a digital economy during the 14th Five-Year Plan eriod（2021-2025）. The plan also emphasized industrial （ ）transformation.
-
- A.digital
- B.networking
- C.intelligentize
- D.informatization
- 查看答案