KMP算法比较次数_设主串 t = abaabaabcabaabc,模式串 s = abaabc,采用 kmp 算法进行

作者：喵喵爱编程 | 2024-07-29 22:41:08

踩

设主串 t = abaabaabcabaabc,模式串 s = abaabc,采用 kmp 算法进行模式匹配,到匹

主串T = “abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法匹配，到匹配成功为止，比较次数是：
序号： 1 2 3 4 5 6
模式串：a b a a b c
next[j]： 0 1 1 2 2 3
关于next数组求法：
前两位为0、1，后面比如第3位，则比较前2个字符串的前后缀公共子串最大长度，比如最后一个c位置，abaab，前缀最大ab，后缀也也是ab，（每个位置结果+1）结果为3。
第一趟：
查看第一趟结束，比较到6号的c，滑动模式串到3号和主串T的6号比。
最终匹配两趟成功，共比较了10次。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/喵喵爱编程/article/detail/900917