求字符串‘abaabcac’的next数组和nextval数组

今天刷到一个笔试题，求一个字符串在KMP算法下的next数组和nextval数组

几番百度和看题解，居然大多数的题解都有毛病被一顿吐槽

几番周折终于搞懂了怎么求next数组和nextval数组，在此记录下

题目是：

求字符串abaabcac的next数组和nextval数组：

结果如下： 注意： 这里的数组下标从1开始数

首先，通过一个动图来了解下求next数组的过程

本图来自

我觉得这张图已经很直观了，下面我就对求解的方法做一点自己的总结

求next数组

next[1] = 0 next[2] = 1 当i > 2 时，如：求next[5] 求next[0]~next[i - 1]所构成的串的首子串和尾子串（首子串不包括最后一个，尾子串不包括第一个） next[0]~next[4]为：abaa 首子串：a，ab，aba 尾子串：baa，aa，a 计算首尾子串中相同的子串的长度 相同的子串为a，长度为1 next[i] = length + 1 求得长度为1,1+1 = 2，所以next[5] = 2

求nextval数组

求nextval[i]的值，我们要比较String[i]和String[next[i]]的值 如果String[i]和String[next[i]]的字符相等，那么nextval[i]的值就等于nextval[next[i]]的值， 如果String[i]和String[next[i]]的字符不相等，那么nextval[i]的值就等于next[i]的值。

就上面的串进行演示：

i = 1 nextval[1] = 0 i = 2 nextval[2] = 1 i = 3 next[3] = 1 String[3] = a String[1] =a == a nextval3] = nextval[1] = 0 i = 4 next[4] = 2 String[4] = a String[2] = b != a nextval[4] = next[4] = 2 同理，可以求出所有的啦

花了一个多小时百度和总结，有了比较深刻的印象了，下次遇到就能轻松应对了