在KMP算法中，next数组（有时也称为fail数组或π数组）用于在发生不匹配时决定模式串应该向右移动多少位。而nextval数组是next数组的一个改进版
首先，定义next数组：
对于模式串P[0..m-1]，next[j]表示P[0..j-1]中最长相同前后缀的长度（不包括整个串自身）。如果这样的前后缀不存在，则next[j] = 0。
next数组的构建通常使用如下算法：
def compute_next(P, M, next):
next[0] = -1
i = 0
j = -1
while i < M - 1:
if j == -1 or P[i] == P[j]:
i += 1
j += 1
next[i] = j
else:
j = next[j]
定义nextval数组：
nextval[j]与next[j]的主要区别在于，当P[j]等于P[next[j]]时，nextval[j]会取next[next[j]]的值，而不是直接取next[j]的值。这是因为在模式串的匹配过程中，如果当前字符相等但下一个字符不相等，那么我们可以跳过更长的前后缀，直接比较下一个字符。
nextval数组的构建通常使用如下算法：
def compute_nextval(P, M, next, nextval):
for i in range(M):
nextval[i] = next[i]
i = 0
while i < M - 1:
if nextval[i] == -1:
i += 1
elif P[i] == P[nextval[i]]:
nextval[i] = nextval[nextval[i]]
i += 1
else:
i += 1
可以查看相关书籍和博客进一步深入认识
