KMP算法的next/nextval值的个人理解

2020-04-0111:51:50数据结构与算法Comments4,249 views1字数 2024阅读模式

学习KMP算法的时候对于next/nextval值的计算总是处在似懂非懂的状态，后面结合了老师的方法和网上的资料自己总结了一下，下面是我自己的一些个人经验，比较浅显易懂，希望能帮到一部分人。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

KMP算法的运行模式

KMP算法与BF算法的最大区别就是，BF算法每次匹配时模式串都是往下一位移动，又重新从模式串的第一位开始比对；而KMP算法的思想是，如果已有一部分字段匹配成功，在这一部分字段中寻找相同的两部分小字段，即概念中的子串，以减少比较次数，提升算法效率。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

但是，

这两部分相同的子串，是有约束条件的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

计算next与nextval值

我们以串测试中的第7题为例，以下方法计算得的next与nextval值均遵循考试规则，可能不同教材有所不同。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

注意：务必看完整个过程，切勿心急

在我们计算之前，要先知道next值的作用是什么。
实际上主串第i个字符与模式串某个字符不匹配后，有两种不同的情况处理：
1.下次比较拿主串第i+1个字符与模式串第1个字符匹配；
2.下次比较依旧拿主串第i个字符与模式串的某个字符比较。
而next值的使用场景为：在KMP算法中，当主串与模式串逐个字符比较时，某个字符不匹配时，则模式串向右移动，移动的位数为next值+1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

首先next[0]的值固定为-1，而next[1]的值固定为0（关于这点后面会有解释）

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

从第j=2开始，看前面的字段有无两段相同的子串。此时前面字段为底色黄色的ab字段（以下情况的前面字段均以黄底标出）

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

很明显没有相同字段，故next[2]的值为0。这也能解释为什么t[1]的next值一定为0，毕竟t[1]前仅有t[0]一个数，根本不可能存在两段相同的子串，所以t[1]的next值必定为0。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

j=3时同样在前面字段中没有两段相同字段，不再赘述。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

当j=4时，如下图

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

可以看出前面字段abca中有两段相同的子串a，用红字标出，故相同字段的长度为1，则next值为1。（以下相同字段均以红字标出）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

继续向下，当j=5时，情况与j=4相同。

当j=6时，如下图

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

可以看出此时前面字段中相同子串为ab，故相同字段长度为2，next值为2。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

接下来，当j=7时

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

可以看出此时前面字段中没有相同子串，故相同字段长度为0，next值为0。但是，有些朋友看到这里会说，如果单纯找前面字段中的相同子串，那像刚刚j=6时的ab字段在这里也符合标准，为什么next值不为2呢？或者，像下面这张图片一样，为什么next值也不是1呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

前缀子串和后缀子串

还记得上文提到的有约束条件的子串吗？
这便是前缀子串与后缀子串
前面的子串，叫前缀子串；同理，后面的子串，叫后缀子串文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

但关键在于，约束条件是什么呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

让我们再观察一下刚刚那些没有问题的子串，也就是前缀子串和后缀子串文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

上面两张图中前缀子串和后缀子串有什么共同点呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

可以发现，前缀子串的第一位均为t[0]
若将此时j的值设为x，后缀子串的最后一位均为t[x-1]
用图形来理解，就是在黄底区域中，前缀子串的第一位必须是黄底区域的第一位，即t[0]；
同样的，后缀子串的最后一位必须是黄底区域的最后一位，即t[x-1]文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

让我们回到j=7的情况中，在了解了前缀子串与后缀子串的定义之后，现在的你理解为什么next[7]=0了吗？

如果你理解了，那么恭喜你，真正掌握了next值的求算方法

观察模式串中的前缀子串和后缀子串，判断出的next值就是准确的。多加练习，就能很快求出next值。下面是完整的表图，大家可以对照着再练习一遍。

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

nextval值的求解

当你对next值的求解驾轻就熟之后，nextval值的求解相比之下就简单很多，除了nextval[0]的值仍为-1，其他nextval值都遵循以下规则：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

不同则同，同则等于

这是什么意思呢？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

下面是题7的nextval值表

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

注意：上表为正确的表，下面例子中的表格中的j=7一栏中的next及nextval值错误，请以上图为准练习文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

我已经标出了所有数的nextval值，接下来让我们看几个例子：

当j=1时

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

t[1]=b，next[1]=0，则我们根据next[1]=0找到t[0]=a，a与b不同，则nextval[1]=next[1]=0，这就是不同则同文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

当j=2时

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

t[2]=c，next[2]=0，则我们根据next[2]=0找到t[0]=a，a与c不同，则nextval[2]=next[2]=0文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

当j=3时

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html

t[3]=a，next[3]=0，则我们根据next[3]=0找到t[0]=a，a与a相同，则nextval[3]=nextval[0]=-1，这就是同则相等，即两字符相同时两者的nextval值相等文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/18019.html