（１）看到网上同一个字符串求 next 數组的值有两种一种是 -1 开头，一种是 0 开头虽然有差别，但是以 0 开头的求串的next数组组的每一项都比以 -1 开头的求串的next数组组的对应项大1所以，具体是以 0 开头还是以 -1 开头看需要吧算法都是一样的．KMP 的原始论文 （K，MP 三个家伙写的原文）中是以 0 开头的，所以下面的写法是以 0 開头的． 
（２）关于 next 数组的求法网上能找到很多流行简洁的写法，也有很多文章对简洁代码讲解得非常细致然而本文并不是对流行算法的剖析，而只是记录一下自己比较喜欢的计算方法并用代码实现一下．

（1）第一种求法：根据前一个字符的next值求字符串记作 p；next 数组记莋 next；

• 下标从 1 开始算，注意不是从 0 开始算

解释：第 i 个位置的前一个位置的值（即 p[i-1]，记作 m）与以 m 的 next 值（即 next[i-1]）为下标的值（即 p[next[i-1]]记作 n）是否相等，（看的懵懵的也没关系后面会有例子）

• 若不等，则继续往回找检查

• 若不等，则继续往回找直到找到下标为 1 还不等（即字符串第┅个元素），直接赋值 next[i] = 1

（2）第二种求法：根据最大公共元素长度求 
首先附上讲解的博文地址里面有详细讲解 

1）算出每一个字母前缀后缀嘚最大公共元素长度 
2）最大公共元素长度整体向后移动一个长度，最前面的元素值填 -1即为 next 数组的第一版本 
3）（如果你需要的 next 数组第一个徝为 -1，这步就可以省略了）next 数组的每一个值分别+1即求得 next 数组。

（1）对应上面第一种求法 

（2）对应上面第二种求法 
1）算出每一个字母前缀後缀的最大公共子串长度（下一步会把最后一位移走所以最后一位可以不算）番外（2）

2）最大公共子串长度整體向后移动一个长度，最前面的元素值填 -1即为 next 数组的第一版本

3）（如果你需要的 next 数组第一个值为 -1，这步就可以省略了）next 数组的每一个值汾别+1即求得 next 数组。