數據結構考研分類復習真題 第四章 答案[9]

　　．（）p的nextval函數值為（p的next函數值為）

　　（）利用KMP(改進的nextval)算法每趟匹配過程如下

　　第一趟匹配 abcaabbabcabaacbacba
　　abcab(i=j=)
　　第二趟匹配 abcaabbabcabaacbacba
　　abc(i=j=)
　　第三趟匹配 abcaabbabcabaacbacba
　　a(i=j=)
　　第四趟匹配 abcaabbabcabaac bacba
　　(成功)             abcabaa(i=j=)

　　．KMP算法的時間復雜性是O（m+n）

　　p的next和nextval值分別為和

　　．（）p的nextval函數值為（next函數值為）

　　（）利用所得nextval數值手工模擬對s的匹配過程與上面題類似為節省篇幅故略去

　　．模式串T的next和nextval值分別為和

　　．第行的p[J]=p[K]語句是測試模式串的第J個字符是否等於第K個字符如是則指針J和K均增加繼續比較第行的p[J]=p[K]語句的意義是當第J個字符在模式匹配中失配時若第K個字符和第J個字符不等則下個與主串匹配的字符是第K個字符;否則若第K個字符和第J個字符相等則下個與主串匹配的字符是第K個字符失配時的下一個（即NEXTVAL[K]）

　　該算法在最壞情況下的時間復雜度O（m）

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22608.html