设目标为t=“abcaabbabcabaacbacba”，模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。

正确答案：① p的nextval函数值为0110132。（p的next函数值为0111232）。 ② 利用KMP（改进的nextval）算法，每趟匹配过程如下：

第一趟匹配：A.caabbabcabaacbacba A.cab（i=5，j=5）

第二趟匹配： A.caabbabcabaacbacba A.c（i=7，j=3）

第三趟匹配： A.caabbabcabaacbacba A.i=7，j=1）

第四趟匹配： A.caabbabcabaac bacba （成功） A.cabaa（i=15，j=8）