您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

KMP算法的个人理解记录

KMP算法介绍参考KMP算法—终于全部弄懂了_June·D的博客-CSDN博客_kmp算法这篇博文。

在此基础上,我记录一些我的理解心路。

        1.首先是next数组的求解过程。当k == -1 或者 t[j] == t[k]时很好理解,就是当前j的next值就相当于j-1的next值再加一。而t[j] != t[k]的情况下,这时候将我们想找的最长公共前后缀分为前缀与后缀考虑:

        前缀是由j-1的最长公共前后缀的某个前缀加上这个前缀后面的一位字符组成

        后缀是由j-1的最长公共前后缀的某个后缀加上t[j]组成。

 

我们要让这个前缀与后缀相等,则第一件事就是要取j-1的最长公共前后缀的某个前缀等于同等长度的后缀,也就是让上面的前缀与后缀的第一部分相等,这即是j-1的最长公共前后缀的最长公共前后缀,这就是k=next(k)的来源。

        2.不同的KMP算法的实现对next的定义是可能有差别的。有的取最长公共前后缀长度为n的next值为n-1,有的为n。此外,有的KMP的next[j]值保存的是0~(j-1)的字符串的最长公共前后缀的长度,有的是0~j。但是本质都一样,只是变换时+1-1的区别。


分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进