KMP算法计算next代码理解

本文主要是介绍KMP算法计算next代码理解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这一篇主要讲计算next代码的理解，默认已经会手算next，如果不会先看看下面这一篇：
手算next的理解

要理解一段代码，最简单的就是跟着代码走一遍

顺代码思路

在这里插入图片描述
可以看出，j的作用相当于是遍历整个字符串，当长度为0、1、2… …
而k的作用则是计算相应长度下的next值。
比较T[j]与T[k]，如果相等，j后移，k加一；否则，j不动，k回溯。、

接下来要了解以下几个问题：
1.为什么比较T[j]和T[k]就行了？
2.k要回溯到哪个位置？

首先是第一个问题：为什么比较T[j]和T[k]。
在这里插入图片描述

以上图序号六那一段为例，比较的是T[3]与T[1]，因为T[2]与T[0]在上一段就比较过了，并且相等，因此这里实际上相当于比较T[3]T[2]与T[1]T[0]是否相等，这一步其实对应next分段函数中的第二种情况。

这样就可以与手算代码相联系一下：
在这里插入图片描述
有没有稍微看明白一点？

接下来是重头戏：第二个问题——k要回溯到哪个位置

以上面顺代码走的最后一步为例：
在这里插入图片描述
现在应该大概能理解这段代码了吧。
设计这个算法的人真是个天才！

这篇关于KMP算法计算next代码理解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！