学习本文需要你已经了解KMP算法的基本思想，即理解通过公共前后缀来进行模式串下标移动的思想（可以参考别的博客，如果需要的话，请在评论区告诉我，后续可能也会补上这一部分）。

Next数组求解

废话不多说，直接讲为什么j=next[j]，这一步是最多人不解的地方。
首先，next数组中记录的是子串中的最大公共前后缀的长度+1，比如下边这个例子。

第6个元素c之前的字符串为“abcab”，最大公共前后缀为“ab”，长度为2，所以next[6]=3。公共前后缀的可以参考下图，箭头就是下标增大的方向：那么当判断一个增加了一个元素的子串的最长公共前后缀时，如果S[j]!=S[i]，那么最大公共前后缀长度必然无法直接+1，可以见下图。

那么此时就是会用到j=next[j]，为什么呢？
我们想一下，既然这个情况不是我们最长公共前后缀了，那么得试着找最长啊，不能放着不管啊。最简单的方法：遍历，每次都让前后缀的长度减一，再试着匹配，但是这样太蠢了，不够simple。所以我们要找简单的方法：先想一下，如果我们找到了这个公共前后缀的话，那么就是下图这个样子：

可以看到，找的话得先找到一个最长的黄色这一部分，如果找到了的话，再比较S[k]与S[i]，如果S[k]=S[i]，那么这就是新的最长公共前后缀了。只有找到黄色这一部分，我们才能有机会比较S[k]与S[i]，那么怎么找呢？我们先把原来上次找到的最长公共前后缀给画回来：
可以看到，因为黄色是 “前缀A的一个前缀”，同时又是 “后缀B的一个后缀”，又因为前缀A=后缀B，所以找黄色部分，本质上就是找上次最长公共前后缀的最长公共前后缀，可以看下图，可能有点绕，请品位一下。
那么这个该怎么求呢？我们求最长公共前后缀的时候是最短到长依次求的，所以之前的结果我们都是有的，是什么？没错，这个长度就是next[j]-1，但是我们要试着比较的是S[k]与S[i]，那么k应该是什么呢？没错k=next[j]！
如果S[k]!=S[i]的话，我们就要再用这种思想再继续找黄色中的最长公共前后缀了。如果S[k]=S[i],我们也就可以得到此时的最长公共前后缀了。

Nextval数组求解

上边我们已经知道了next数组是怎么求解的，那么nextval数组是什么意思呢？下述符号含义与上述符号独立，别搞混了。
我们知道在KMP算法中，是对主串T用模式串S进行匹配，当T[i]!=S[j]时，比较T[i]与S[next[j]]。如果S[j]=S[next[j]]，那么T[i]!=S[next[j]]必然成立，再比较的话这不浪费时间吗，我们又知道完整的模式串中的每一个字符，可以提前知道S[j]=S[next[j]]是否成立，所以我们利用这个信息对next数组进行改进：
如果S[j]=S[next[j]]，那么我们可以直接比较T[i]与S[next[next[j]]]（KMP算法思想的迭代）
表现在nextval数组上就是:若S[j]=S[next[j]]，则next[j]=next[next[j]]

总结

上述只是本人在学习KMP算法时的一些心得体会，如果有错误还请在评论区指正。此外，如果觉得我有哪里讲述不清楚的地方，也可以在评论区告诉我，我也会试着再改进（感觉nextval这里因为有公式，所以还挺丑的hhh）。如果解决了你的疑惑的话，也可以给我点赞加收藏。