kmp算法求next 和 nextval

KMP算法是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。其中，next数组和nextval数组是KMP算法中的两个重要数组。

next数组是模式串P的最长公共前后缀长度数组，用于在匹配过程中避免重复匹配。具体来说，next[i]表示P[:i]的最长公共前后缀长度，即P[:next[i]] = P[i-next[i]:i]。

nextval数组是next数组的改进版，用于在匹配过程中更快地跳过不匹配的部分。具体来说，nextval[i]表示当P[i]与S[j]不匹配时，下一次匹配应该从P[nextval[i]]开始，即P[:nextval[i]]与S[j-nextval[i]:j]是相等的。

求解next和nextval数组的方法是相同的，都是通过递推计算得到。具体来说，对于next数组，我们从i=1开始，依次计算next[i]，直到i=n-1为止；对于nextval数组，我们需要先求出next数组，然后再从i=1开始，依次计算nextval[i]，直到i=n-1为止。