![](https://csdnimg.cn/release/download_crawler_static/88616937/bg4.jpg)
13.next 定义见题上面 6 和下面题 20。串 p 的 next 函数值为:01212345634。
14.(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)
15 .( 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)
16.KMP 算法的时间复杂性是 O(m+n)。
p 的 next 和 nextval 值分别为 01112212321 和 01102201320。
17.(1)p 的 nextval 函数值为 01010。(next 函数值为 01123)
(2)利用所得 nextval 数值,手工模拟对 s 的匹配过程,与上面 16
题类似,为节省篇幅,故略去。
18.模式串 T 的 next 和 nextval 值分别为 0121123 和 0021002。
19.第 4 行的 p[J]=p[K]语句是测试模式串的第 J 个字符是否等于第 K 个