数据结构
合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下
——老子
1
每日一练
1．设字符串 S=‘aabaabaabaac’，P=‘aabaac’
（1）给出 S 和 P 的 next 值和 nextval 值；
（2）若 S 作主串，P 作模式串，试给出利用 BF 算法和 KMP 算法的匹配过程。
2．设目标为 t=‘abcaabbabcabaacbacba’,模式为 p=‘abcabaa’
（1）计算模式 p 的 naxtval 函数值；
（2）不写出算法,只画出利用 KMP 算法进行模式匹配时每一趟的匹配过程。
正确答案
PS：||代表注释
1．
（1）S的next与nextval值分别为012123456789和002002002009，p的next与nextval值分别为012123和
002003。
（2）利用BF算法的匹配过程： 利用KMP算法的匹配过程：
第一趟匹配： aabaabaabaac 第一趟匹配：aabaabaabaac
aabaac(i=6,j=6) aabaac(i=6,j=6)
第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac
aa(i=3,j=2) (aa)baac
第三趟匹配： aabaabaabaac 第三趟匹配：aabaabaabaac
a(i=3,j=1) (成功) (aa)baac
第四趟匹配： aabaabaabaac
aabaac(i=9,j=6)
第五趟匹配： aabaabaabaac
aa(i=6,j=2)
第六趟匹配： aabaabaabaac
a(i=6,j=1)
第七趟匹配： aabaabaabaac
(成功) aabaac(i=13,j=7)
2．
（1）p的nextval函数值为0110132。（p的next函数值为0111232）。
（2）利用KMP(改进的nextval)算法，每趟匹配过程如下：
第一趟匹配： abcaabbabcabaacbacba
abcab(i=5,j=5)
第二趟匹配： abcaabbabcabaacbacba
abc(i=7,j=3)
第三趟匹配： abcaabbabcabaacbacba
a(i=7,j=1)
第四趟匹配： abcaabbabcabaac bacba
(成功) abcabaa(i=15,j=8)
-end-