数据结构考研分类复习真题 第四章 串[8]

．设字符串S=aabaabaabaacP=aabaac【北方交通大学二（分）】

（）给出S和P的next值和nextval值

（）若S作主串P作模式串试给出利用BF算法和KMP算法的匹配过程

．设目标为t=abcaabbabcabaacbacba模式为p=abcabaa【清华大学 八（分）】

（）计算模式p的naxtval函数值（分）

（）不写出算法只画出利用KMP算法进行模式匹配时每一趟的匹配过程（分）

．模式匹配算法是在主串中快速寻找模式的一种有效的方法如果设主串的长度为m模式的长度为n则在主串中寻找模式的KMP算法的时间复杂性是多少？如果某一模式 P=abcaacabaca请给出它的NEXT函数值及NEXT函数的修正值NEXTVAL之值【上海交通大学 一 （分）】

．设目标为S=abcaabbcaaabababaabca模式为P=babab【清华大学 四（分）】

（）手工计算模式P的nextval数组的值(分)

（）写出利用求得的nextval数组按KMP算法对目标S进行模式匹配的过程 (分)

．用无回溯的模式匹配法（KMP法）及快速的无回溯的模式匹配法求模式串T的next[j]值添入下面表中【北京邮电大学 三（/分）】

．在改进了的（无回溯）字符串模式匹配中要先求next数组的值下面是求nextval值的算法【北京邮电大学 二（分）】

TYPE SAR=ARRAY[m] OF INTEGER;

PTY=ARRAY[m] OF CHAR;

PROCEDURE next(P:PTY;VAR NEXTVAL:SAR);

{在模式P中求nextval数组的值}

BEGIN

J:=;NEXTVAL[]:=;K:=

REPEAT

IF (K=) OR (P[J]=P[K])

THEN [ J:=J+;K:=K+;

IF P[J]=P[K]

THEN NEXTVAL[J]:=NEXTVAL[K]

ELSE NEXTVAL[J]:=K ]

ELSE K:=NEXTVAL[K]

UNTIL J=m

END;

算法中第行有P[J]=P[K]第六行中也有P[J]=P[K]两处比较语句相同请分析说明此两处比较语句的含义是什么？分析此算法在最坏情况下的时间复杂度是多少？

[] [] [] [] [] [] [] [] [] [] [] []