KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
第1题:
已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”。采用KMP算法进行匹配,第一次出现“失配”(s[i]≠t[j])时,i=j=5,则下次开始匹配时,i和j的值分别是()。
A.i=1,j=0
B.i=5,j=0
C.i=5,j=2
D.i=6,j=2
第2题:
A.BCd
B.Bcd
C.Abc
D.ABC
第3题:
设主串长为n,模式串长为m(m≤n),则在匹配失败的情况下,朴素匹配算法进行的无效位移次数为(30)。
A.m
B.n-m
C.n-m+1
D.n
第4题:
● 在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特—福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式串的长度分别为n和m(且n远大于m),且恰好在主串末尾的m个字符处匹配成功,则在上述的模式匹配过程中,字符的比较次数最多为(57)。 A.n*m B.(n-m+1)*m C.(n-m-1)*m D.(n-m)*n
第5题:
●在KMP模式匹配算法中,需要求解模式串p的next函数值,其定义如下(其中,j为模式串中字符的序号)。对于模式串“abaabaca”,其next函数值序列为(57)。
(57)
A. 01111111
B.01122341
C.01234567
D.01122334
第6题:
第7题:
当运用改进的模式匹配算法时,模式串P='ABAABCAC'的next函数值序列为(41)。
A.1222312
B.1122312
C.1122212
D.122312
第8题:
●在字符串的模式匹配过程中,如果模式串的每个字符依次和主事中一个连续的字符序列相等,则称为匹配成功。如果不能在主串中找到与模式串相同的子串,则称为匹配失败。在布鲁特—福斯模式匹配算法(朴素的或基本的模式匹配)中,若主串和模式串的长度分别为n和m(且n远大于m),且恰好在主串末尾的m个字符处匹配成功,则在上述的模式匹配过程中,字符的比较次数最多为(57)。
(57) A. n*m
B. (n-m+1)*m
C. (n-m-1)*m
D. (n-m)*n
第9题:
设主串长为n,模式串长为m(m≤n),则在匹配失败情况下,朴素匹配算法进行的无效位移次数为 ( )
A.m
B.n-m
C.n-m+1
D.n
第10题:
试题四(共15分)
阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。
【说明】
模式匹配是指给定主串t和子串s,在主串t中寻找子串s的过程,其中s称为模式。
如果匹配成功,返回s在t中的位置,否则返回-1 。
KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下:
1.在串t和串s中,分别设比较的起始下标i=J=O
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:长度为悯铂Is的字符串
next:next数组,长度为Is
(2)C程序
include <stdio.h>
nclude <stdliB.h>
include <string.h>
/*求next【】的值*/
void get_next( int *next, char *s, int Is) {
int i=0,j=-1;
next[0]=-1;/*初始化next[0]*/
while(i< ils){/*还有字符*/
if(j=-1l ls[i]=s[j]){/*匹配*/
j++;
i++;
if( s[i]一s[jl)
next [i]- next[j];
else
Next[i]=j;
}
else
J= next[j];
}
}
int kmp( int *next, char *t ,char *s, int.lt, int Is )
{
inti= 0,j =0 ;
while (i<lt && ( 1 ) {
if( j=-1 II 2_) {
i++ ;
j ++ ;
} else
(3) :
}
if (j>= ls)
Retum (4)
else .
retum-1;
【问题1】(8分)
根据题干说明,填充C代码中的空(1)~(4).
【问题2】(2分)
根据题干说明和C代码,分析出kmp算法的时间复杂度为 (5)(主串和子的长度分别为It和Is,用O符号表示)。
【问题3】(5分)
根据C代码,字符串“BBABBCAC”的next数组元素值为 (6) (直接写素值,之间用逗号隔开)。若主串为“AABBCBBABBCACCD”,子串为“BBABBCAC则函数Kmp的返回值是 (7)