．設字符串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]兩處比較語句相同請分析說明此兩處比較語句的含義是什麼？分析此算法在最壞情況下的時間復雜度是多少？
[] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/22579.html
