KMP算法：
1、文本串、模式串：要在文本串：
aabaabaafa 中查找是否出现过一个模式串：aabaaf。
2、前缀表：
记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。能告诉我们 上次匹配的位置，并跳过去。
3、最长相等前后缀：
前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。
对于模式串 aabaaf，相同前后缀长度为：
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaaf 0
a a b a a b a a f a 文本串
0 1 2 3 4 5 模式串
a a b a a f
0 1 0 1 2 0
下标5之前这部分的字符串（也就是字符串aabaa）的最长相等的 前缀 和 后缀字符串是 子字符串aa ，因为找到了最长相等的前缀和后缀，匹配失败的位置是 后缀子串 的后面（f），那么我们找到与后缀aa相同的前缀aa的 后面（b）重新匹配就可以了。
4、next数组：
就是前缀表，也可以是前缀表统一减一（右移一位，初始位置为-1）。
核心：遇见冲突（f）就回退！
假设 i 是后缀末尾，j 是前缀末尾：
前后缀不相等就回退，前后缀相等就更新next数组的值，最终得出next数组。
文本串：a a b a a b a a f a
模式串：0 1 2 3 4 5
a a b a a f
0 1 0 1 2 0 最长相等前后缀： 取最长相等前后缀的值作为索引 2
-1 0 1 0 1 2 右移一位： 取冲突位置的索引 2
-1 0 -1 0 1 -1 都-1： 取最长相等前后缀的值+1 作为索引 2
28.找出字符串中第一个匹配项的下标的C++代码：
class Solution {
public:
void getNext(vector<int>& next, const string &s){ //vector<int>& next 引用方式相当于起别名
//1、初始化
int j = 0;
next[0] = j;
// i后缀末尾，j前缀末尾
for (int i = 1; i < s.size(); i++){
//2、前后缀不相等
while (j > 0 && s[i] != s[j]){
j = next[j-1];
}
//3、前后缀相等
if (s[i] == s[j]){
j++; //前后缀相等了要++
}
next[i] = j; //j就是相等前后缀的长度
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0){
return -1;
}
vector<int> next(needle.size()); //next数组和needle字符串一样大
getNext(next, needle); //传入next首元素的地址 和 needle字符串，计算needle字符串的前缀表
cout << next[0] << endl;
int j = 0;
for (int i = 0; i < haystack.size(); i++){
while (j > 0 && haystack[i] != needle[j]){
j = next[j-1]; //j>0 防止数组越界
}
if (haystack[i] == needle[j]){
j++;
}
if (j == needle.size()){
return (i-needle.size()+1);
}
}
return -1;
}
};
补充知识：关于 getNext(&next[0], needle);
在 C++ 中，传递数组给函数时，可以直接传递数组名或者数组的指针。这是因为数组名本身就是数组的地址，而数组在内存中是连续存储的，因此可以通过数组名或数组的指针来访问数组的元素。
例如，对于一个数组 int a[]，你可以直接将 a 作为参数传递给函数，因为 a 本身就是数组的地址。在函数内部，可以通过该地址访问数组的元素。
但是对于 vector 这样的容器类，情况略有不同。vector 是一个类模板，它封装了动态分配的连续内存块，而不像数组那样是静态分配的。因此，传递 vector 对象时，一般需要使用其指针或引用来访问。
因此，如果函数形参是vector & next，那么实参就直接传next（相当于引用别名的方式传参）；
如果函数形参是int* next，那么实参就是&next[0]，把首元素地址传过去，然后用一个in类型的指针指向它。个人建议用引用方式，更容易理解也安全。