再回到next[i]的定义，对于字符串ptr = "ababaaababaa";

next[1] = -1,代表着除了第一个元素，之前前缀后缀最长的重复子串，这里是空 ,即""，没有，我们记为-1，代表空。（0代表1位相同，1代表两位相同，依次累加）。

next[2] = -1，即“a”，没有前缀与后缀，故最长重复的子串是空，值为-1；

next[3] = -1，即“ab”，前缀是“a”，后缀是“b”，最长重复的子串“”；

next[4] = 1，即"aba"，前缀是“ab”，后缀是“ba”，最长重复的子串“a”；next数组里面就是最长重复子串字符串的个数

next[5] = 2，即"abab"，前缀是“aba”，后缀是“bab”，最长重复的子串“ab”；

next[6] = 3，即"ababa"，前缀是“abab”，后缀是“baba”，最长重复的子串“aba”；

next[7] = 1，即"ababaa"，前缀是“ababa”，后缀是“babaa”，最长重复的子串“a”；

next[8] = 1，即"ababaaa"，前缀是“ababaa”，后缀是“babaaa”，最长重复的子串“a”；

next[9] = 2，即"ababaaab"，前缀是“ababaaa”，后缀是“babaaab”，最长重复的子串“ab”；

next[10] = 3，即"ababaaaba"，前缀是“ababaaab”，后缀是“babaaaba”，最长重复的子串“aba”；

next[11] = 4，即"ababaaabab"，前缀是“ababaaaba”，后缀是“babaaabab”，最长重复的子串“abab”；

next[12] = 5，即"ababaaababa"，前缀是“ababaaabab”，后缀是“babaaaababa”，最长重复的子串“ababa”；

 

还有另外一种方法，我看的有的书上写着：

这里我们定义next[1] = 0 , next[1] = 1;

 

再分析ptr字符串，ptr = "ababaaababaa";

跟上一个的情况类似，

 

next[1] = 0 ,事先定义好的

next[2] = 1 ,事先定义好的

next[3] = 1 ,最长重复的子串“”；1代表没有重复，2代表有一个字符重复。

next[4] = 2 ，最长重复的子串“a”；追偿的长度加1，即为2.

next[5] = 3 ，以下都跟之前的一样，这种方法是最长的长度再加上一就可以了。

next[6] = 4

next[7] = 2

next[8] = 2

next[9] = 3 

next[10] = 4 

next[11] = 5 

next[12] = 6 

 

以上是next数组的详细解释。next数组求值 是比较麻烦的，剩下的匹配方式就很简单了。

 

 

参考  

1.https://blog.csdn.net/qq_30974369/article/details/74276186

2.https://blog.csdn.net/starstar1992/article/details/54913261