对kmp算法的理解中，很重要的一点就是next数组。
很多人不理解next数组的含义，是因为它同时具有两个意思，而且这两个意思在不同的环境下不同。
现在给你两个字符串：
一个是文本串 text
一个是模板串 pattern
然后定义两个指针，指针i 指向文本串。指针 j 指向模板串。
现在我们要找模板串在文本串中第一次出现的位置。
那么直接从文本串的第一个字符和模板串的第一个字符开始匹配。（i=text[0] , j=pattern[0])
如果i，j匹配成功（即 text[i] == pattern[j] )?
那么i，j都往右移动。
如果i , j 匹配不成功，那么我们希望 j能重新跳到模板串的某一个位置，重新开始匹配。
（这里不能让i跳，因为 i的变化必须保持是线性的）
如果我们能让 j 具备这样的功能的话，那么匹配字符串将是线性复杂度。
那么我们就提出了一个next数组，希望它能做到这件事。
不过要理解kmp
我们要搞清楚，next数组有什么含义？
- 如果i指针指向的字符 和 j指针指向的字符匹配失败，j指针应该去的位置（这里指的是j指针应该回到模板串的哪个下标）
- next[k] 表示在模板串中从0开始到下标为k，也就是[0,k]的字符串中，最长相等前后缀的长度。
为什么这样说？
其实，我们一开始定义next数组的时候，单纯的希望它有一个功能，就是如果文本串和模板串发生不匹配，那么指针j 去往的地方是 next[j-1] 。
(因为我们现在正在匹配 j ，说明j-1 是已经匹配成功了的，所，
然后我们在求解 next数组的时候发现：
next[k] 的值和? “在模板串中从0开始到下标为k的字符串中，最长相等前后缀“ 的长度相等。
说明我们就可以通过这个特点来求解next数组。
什么意思呢？ 假设我们现在已经求好了next数组的值，那么我们是不是可以根据next数组的含义（如果i指针指向的字符 和 j指针指向的字符匹配失败，j指针应该去的位置）
来写出kmp主函数？
int kmp(string text, string pattern) {//文本串，模板串
//分别表示文本串和模板串的长度
int tlen = text.size();
int plen = pattern.size();
vector<int > next=get_next(pattern);//next数组
//假设我们已经得到了next数组，由于next数组的一个含义是，当匹配失败，模板串指针前往的位置
//所以我们可以写出
int j = 0;
for (int i = 0; i < tlen; i++) { //遍历一遍文本串，以线性的时间复杂度求出匹配位置
if (pattern[j] == text[i]) {//如果匹配了，那么j，i都往右边移动
j++;
if (j == plen) { //如果模板串全部都匹配上了
return i - j;//直接返回第一次匹配成功的下标
}
}
else {//如果没匹配上
if (j > 0) { //如果j大于0
j = next[j - 1]; //j前往应该去的地方
}
//否则，如果j等于0，那么它无处可以去。
}
}
return -1; //如果扫完了一遍文本串还没匹配，直接返回-1
}
很好，根据next的数组的第一个含义我们能求出kmp函数。
但是我们怎么求next数组？ 只需要将next数组的性质结合起来即可。
在求next的数组中需要转变两种观点：
当不匹配的时候，把pattern[0,i]当作文本串、把patter[0,j] 看作模板串，就按照上面kmp的步骤来即可。当不匹配，直接让j=next[j-1]；
当i，j匹配， 那么说明 [0,j-1]肯定是已经匹配上了的（前提是j>0)，又[0,j-1]的长度是 j
现在j也匹配上了，那么最长相等前后缀长度不就 j+1 吗。
(也可以理解成如果 i，j 匹配上了，那么next[i]=next[i-1]+1、 因为匹配成功了一个新字符，那么最长公共前后缀长度+1）
所以啊，如果我们这样想的话，那么next数组也求完了。
vector<int > get_next(string pattern) { //求next数组，并返回next数组
int plen = pattern.size();
vector<int> next(plen);
int i = 1, j = 0; //此时我们将[0,i]当作文本串，将[0,j]的串当作模板串
for (int i = 1; i < plen; i++) {
while (j > 0 and pattern[i] != pattern[j]) { //如果不匹配，那么j就退到应该去的，直到退到0，或者退到二者匹配
j = next[j];
}
if (pattern[i] == pattern[j]) { //这里的话，next就代表[0,i]区间的最长公共前后缀
next[i] = ++j;
}
}
return next;
}
?然后，把二者合起来就是完整的板子了。