2023年7月20日发(作者：)

若S作主串，P作模式串，试分别写出利⽤BF算法和KMP算法的匹配过程。⽬ 录题⽬：设字符串S=‘aabaabaabaac'，P=‘aabaac'（1）给出S和P的next值和nextval值；（2）若S作主串，P作模式串，试分别写出利⽤BF算法和KMP算法的匹配过程。（可以参考 课本80页 图4.3、图4.4的匹配过程描述形式。在每⼀趟匹配后⾯ 备注该趟结束时i和j的值。）百度⽂库-答案（1）S的next与nextval值分别为和，p的next与nextval值分别为012123和002003。（2）MOOC标准答案：

（1）S的next与nextval值分别为和，p的next与nextval值分别为012123和002003。（2）利⽤BF算法的匹配过程：第⼀趟匹配： aabaabaabaac

aabaac(i=6,j=6)

第⼆趟匹配： aabaabaabaac

aa(i=3,j=2)

第三趟匹配： aabaabaabaac

a(i=3,j=1)

第四趟匹配： aabaabaabaacaabaac(i=9,j=6)第五趟匹配： aabaabaabaac aa(i=6,j=2)第六趟匹配： aabaabaabaac a(i=6,j=1)第七趟匹配： aabaabaabaac(成功) aabaac(i=13,j=7)

利⽤KMP算法的匹配过程：第⼀趟匹配：aabaabaabaac aabaac(i=6,j=6)第⼆趟匹配：aabaabaabaac(aa)baac第三趟匹配：aabaabaabaac(成功) (aa)baacmooc答案-截图： 数据结构(C语⾔版)-严蔚敏2007