数据结构考研分类复习真题 第四章 答案[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）

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