引入：如何设计一个算法，判断一个字符串中含有另一个字符串呢？比较容易想到的就是朴素模式匹配算法，时间复杂度是O(n*m)，但是kmp算法可以让时间复杂度降低到O(n)。
这是如何做到的？
假设有两个字符串为
A=ababbababa
B=ababa
不妨令A为主串，B为模式串，可以发现，A[5]和B[5]（不妨设下标从1开始）失配了，如果按照朴素模式匹配算法思想，那么下面该进行比较的字符是A[2]和B[1]。实际上，并不需要这样做，我们只需要将A[5]和B[3]相比较即可*，为什么？
当第n个字符匹配失败时，我们知道前n-1个字符一定是匹配成功的，也就意味着我们只需要研究模式串前n-1个字符就可以了，而指向主串第n个字符的指针不需要回溯来和模式串比较，因此我们可以让下一次比较是主串第n个字符和模式串前n-1中的一个字符来比较，那么让模式串中的哪个字符来比较呢？这就不得不提到（前n-1个字符的）最长公共前后缀和next数组了。
上面我们提到了，让模式串中的哪个字符来比较，即是第 next[n] 个字符，那么next数组又怎么求呢？
1.当j=1时，意味着模式串第一个字符与主串失配，next值为0，我们规定了下标从1开始，这并不表示模式串中第0个字符与主串中的失配字符相比较，而是表示模式串第一个字符与主串失配字符的下一字符再进行匹配。
2.当存在长度为k的公共前后缀，且 0 < k < j-1 时，next值为k+1。
3.当只存在长度为k的公共前后缀（此时k = j-1）时，next值为1，表示模式串第一个字符与主串失配字符相比较。
为什么？可在朴素模式匹配算法中观察规律得出
next数组的进一步优化，nextval
根据上面的公式，我们可以求出B的next数组为 0 1 1 2 3，这就是为什么 "只需将A[5]和B[3]相比较即可"。实际上可以进一步优化，因为我们发现B[5]和B[3]对应的字符都是a，再比较还是会失配，因此我们可以把next[5]的值改为next[3]，而next[3] = 1，我们又发现B[1]还是a，还是会失配，因此我们可以把next[5]改为next[1]，值为0，表示B[1]与A[6]相比较。同样的道理，用这种方法，我们遍历一遍next数组，让next数组优化一下。
代码
求next数组
上面求next方法为手算，代码求next方法参考视频https://www.bilibili.com/video/BV16X4y137qw/
根据前面的介绍容易知道，next[1] = 0, next[2] = 1,
此时若ch[1] == ch[2]，根据next数组定义，next[3] = 2，若ch[2] == ch[3]，则next[4] = 3 ·········直到
ch[n-1] !=ch[n]，则可视为s1s2···sn-1 与s2s3···sn匹配失败，而s1s2···s[next[n-1]-1]与s[n-(next[n-1]-1)]····sn-1是相同的，此时再比较sn和s[next[n-1]]，若相等，则next[n+1] = next[n-1]+1，否则，再按匹配失败走，若是最坏的情况一直失败，j会等于0，最后next[n+1] = 1。
void GetNext(String T ,next[]){
int i=1,j=0;
next[1]=0;
while(i<T.length){
if(j==0||T.ch[i]==T.ch[j]){
++i;
++j;
next[i]=j;
}
else
j=next[j];
}
}
求nextval数组
