现有主串:a b a a b a b a a b a b a b a c a, 模式串:a b a b a c 。请写出模式串的next函数,画出用KMP方法进行匹配的过程,并统计出比较的次数。
时间: 2024-05-30 19:08:19 浏览: 84
模式串的next数组为:[-1, 0, 0, 1, 0, 0]。
匹配过程如下:
1. 在主串中匹配到第一个字符 a,模式串匹配到第一个字符 a,比较次数为1。
2. 在主串中匹配到第二个字符 b,模式串匹配到第二个字符 b,比较次数为2。
3. 在主串中匹配到第三个字符 a,模式串匹配到第三个字符 a,比较次数为3。
4. 在主串中匹配到第四个字符 a,模式串匹配到第四个字符 b,不匹配,模式串向前移动2个字符,比较次数为3。
5. 在主串中匹配到第五个字符 b,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为4。
6. 在主串中匹配到第六个字符 a,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为5。
7. 在主串中匹配到第七个字符 b,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为6。
8. 在主串中匹配到第八个字符 a,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为7。
9. 在主串中匹配到第九个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为8。
10. 在主串中匹配到第十个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为9。
11. 在主串中匹配到第十一个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为10。
12. 在主串中匹配到第十二个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为11。
13. 在主串中匹配到第十三个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为12。
14. 在主串中匹配到第十四个字符 b,模式串匹配到第二个字符 b,不匹配,模式串向前移动1个字符,比较次数为13。
15. 在主串中匹配到第十五个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为14。
16. 在主串中匹配到第十六个字符 c,模式串匹配到第二个字符 c,不匹配,模式串向前移动1个字符,比较次数为15。
17. 在主串中匹配到第十七个字符 a,模式串匹配到第一个字符 a,不匹配,模式串向前移动1个字符,比较次数为16。
因此,匹配过程一共进行了16次比较。