从零开始的数据结构学习日记（九）——1.9KMP算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了从零开始的数据结构学习日记（九）——1.9KMP算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1995字，纯文字阅读大概需要3分钟。

内容图文

1.1KMP算法

先给出KMP算法伪代码：
1.在目标串T和模式串P中分别设置比较的起始下标i和j
2.当(i<n&&j<m)时，重复以下操作，直到目标串T或者模式串P的字符都比较完毕
——2.1如果T[i]等于p[i]，则继续比较T和P的下一对字符
——2.2否则将模式串P的下标j回溯到P中的next[j]位置，即j=next[j]
——2.3如果j=-1，则将下标i和j分别加1，准备下一趟比较
3.如果P中所有的字符均比较完成，则匹配成功，返回最后一趟匹配开始位置；否则匹配失败返回0
计算next数组的算法伪代码如下：
1.赋初值j=0；k=-1；next[0]=-1
2.当j<length§时，重复以下操作，直到模式串P中所有字符均处理完毕
——2.1如果k=-1或者pj等于pk，分别将j和k加1，然后将k赋给next[j]
——2.2否则将next[k]赋给k
3.返回next数组的值
浏览csdn发现如下好办法：

下面介绍一到北邮2016年考研真题
1 2 3 4 5 6 7 8
a b a a b c a c
0 1 1 2 2 3 1 2
这是一个考试常见的字符串，是如何计算的那？
第n位：next[n]的值来自于第n-1位的字符，通过跟第next[n-1]位字符比较，如果相同next[n]=next[n-1],如果不相同，就跟第next[next[n-1]]位的字符比较，就这样迭代直到相同的时候，加上1，如果实在没有，就为1.
这一段话可能很难理解，逐位分析。
让我们从依次来看：
第3位：第2位和第1位比较，不相同 所以为1
第4位：第3位和第1位比较，相同，所以为2
第5位：第4位和第2位比较，不相同，和第1位比较，相同，所以为2
第6位：第5位和第2位比较， 相同，所以为3
第7位：第6位和第3位比较，不同，和第1位比较，不同，所以为1
第8位：第7位和第1位比较，相同，所以为2.
这就是next数组的手动计算方法。
————————————————
版权声明：本文为CSDN博主「qq_37747664」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_37747664/article/details/82734448

如果这个方法还是不能理解，笔者这里有一个自用的玄学 办法描述如下：
我们观察要计算next数组的字符串的头和尾，比如所引文章中的“abaabcac”，前两位为0和1，第三位因为前两位不相同为1，第四位的数组因为“aba”子串的前缀和后缀有一个相同的字母a所以为2，第五位因为子串“abaa”前缀后缀中有一个a相同所以为2，第六位因为子串“abaab”前后缀中有ab相同所以为3，以此类推。

• 点赞
• 收藏
• 分享
• • 文章举报

The wind of freedom 发布了9 篇原创文章 · 获赞 1 · 访问量 273 私信 关注

内容总结

以上是互联网集市为您收集整理的从零开始的数据结构学习日记（九）——1.9KMP算法全部内容，希望文章能够帮你解决从零开始的数据结构学习日记（九）——1.9KMP算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---