如何求next数组呢？
方法
对于一个点i来说要求他的next数组，那么我们需要找到他前面和他相同的一个点，如果没有找到这个点那就继续往前找，知道某个点与他的值相等。这里有个小问题就是为什么1到这个点的字符串是完美符合最长子串这个条件的呢？原因是由于前面的几个数据都是相同的，如果这个时候的j=next[j]，那么是可以完美保证这一段数据前面是相同的，无法保证的是next[j]后面的数据是否和s[i]相同，也正是因为这个原因，所以可以对比。直到这个j和n一样大，这个时候就完美地找到了第一串完全相同的字符串。
next[i]=j的含义是,以i为重点的一段模板,他的最长后缀长度是j.与此同时如果直接让j=next[j],意思其实就是让j直接跳到了下一个最长的模板长度处,如下图,此时s[i]就是在和next[j]直接作比较。
作者解释next数组解释得好，顶一个。
那我也说说我对next[]数组的理解吧
举个栗子：
子串a[j]：......caab......caaa........caab
主串s[i]：...................................caaa.......
假设子串与主串前面一部分都相等，当子串与主串枚举到的字母不相等即s[j+1]!=s[i]时(栗子中子串字母b!=主串字母a)，就将j往回跳到next[j]的位置(j=next[j])，此时next[j]的位置就是子串......caab......caa最后一个a的下标，按next数组定义知子串中的字母......caab......caa一定与子串中的字母........caa的一部分相等，即子串中字母......caab......caa是主串中字母........caa的子集，当跳到next[j]的位置后，比较a[i]与s[j+1]，发现相等，则再往后比较，直到把s数组遍历完。
那么next数组是怎样存储的呢？
我们举个简单的栗子：caaacaab
首先先明确首字母的next[1]=0，因为首字母的前面没有字母可以与其匹配，此时i从2开始，j=0(技巧）,按定义if(p[i] == p[j+1]) j=j+1；next[i] = j；可知next[1~4]=0，当i=5时s[i]=s[j+1]，则next[5]=1，以此类推next[6]=2，next[7]=3....由此定义，可见只要next[j]!=0(为了与i区别，故j。next[i]=0时则退回到首字母)，next[0~j]中一定与caaacaab中某一部分相等，此过程就像把自已中有重复字母的一部分当做子串，自已当主串，求next数组的值。
由此，我们推广到一般情况：......caab......caaa........caab，我们寻找此子串的next数组。
我们找最后一个b的next的值，按逻辑(while(j && p[i] != p[j+1]) j = next[j],自已当模板) 知......caab......caaa........caa最后一个a的next[i]的值可能等于......caab......caa中最后一个a的下标j，于是将j跳到next[j] (j=next[j])，然后再比较s[j+1]与s[i]，发现不相等，则再将j跳到next[j] (j=next[j])，此时j可能就是......caa最后一个下标a的值，再比较s[j+1]与s[i]，发现相等，则令b的next[i]=j+1；这样，我们就求出了子串的next数组的值。