代码随想录-B站视频
KMP ：三位学者首字母，用于匹配字符串。
时间消耗：O(m+n)。
文本串：需要在其中查找模式串。
模式串：不匹配时，不会直接从文本串的下一个字符，而是直接跳到当前已经匹配好的串后继续匹配。
前缀表：一个字符串中每个字符的最长相等前后缀。
前缀：包含首字母，不包含尾字母的所有字串。
后缀：包含尾字母，不包含首字母的所有字串。
最长相等前后缀：
例子：aabaaf
a:是前缀没有后缀，0;
a : aa的长度是1；
b:aab长度是0；
a:aaba长度是1；
a:aabaa长度是2；
f:abaaf长度是0。
a至此得到前缀表：[0,1,0,1,2,0]。
过程：当f不匹配时，查找表发现，前一个位置对应的最长相等前后缀是2，这就是不相等了需要继续去匹配的字符串的位置，相等于跳到前缀的后面，这里就是继续去匹配b的意思。
next（prefix）数组：就是前缀表，表示遇见冲突后next数组会告诉我们需要回退到哪里。
（直接用前缀表就可以实现KMP算法，但是有的实现会进行一些转变）实现过程中会将前缀表进行减一或者右移一位，效果都是初始位置变为-1，后面整体右移或者减一，相当于变成[-1,0,1,0,1,2]或者[-1,0,-1,0,1,-1]。就像上面的在f发生冲突看的是前一位的前缀表，因此整体右移可以直接实现当前位置的匹配，减一个也是访问前一个位置的前缀表，然后再找的时候将这个1再加回来。
实现：循环不变量：遇见冲突看前一位。
next数组：
- 定义函数来求next数组，传入next数组，传入模式串
- 初始化next数组和函数中各个变量。需要一个指向前缀末尾位的j和指向后缀末尾位置的i，这里的j还代表了包括i在内的最长相等前后缀的长度。j=0；next[0]=0。
- 处理前后缀不相同的情况。从i开始进入循环遍历到模式串全部长度，i=1开始，因为i不能和j相等。比较当前的j和i，两者不相等时需要回退（不止一步，while），回退到前一位的前缀表对应的位置（相当于匹配时出现了冲突，j=next[j-1]，更仔细地说就是当前已匹配上的字串中（也就是当前已经匹配上的后缀中）可以不用再匹配的长度），回退到0停止( j!=0 and s[i]!=s[j] )。
- 处理前后缀相同的情况。s[i]=s[j]时相当于匹配上了，j需要加一，相当于匹配上一个。
- 更新next数组的值。最后更新next[i]=j。
