LeetCode KMP 算法

可以参考

https://www.bilibili.com/video/BV1AY4y157yL/

kmp 主要做的就是子串匹配，类似C程序的 strstr() 函数

记录一下，也防止我自己忘记

传统暴力求解算法是

源串 ssssssssa
子串 sssa（下面暴力求解）
先 (子串从 0 位置匹配，并且匹配到最后一个字符才发现不对，白搞)
ssssssssasssa其次 (子串从 0 位置匹配，并且匹配到最后一个字符才发现不对，白搞)
ssssssssasssa再后面就是 (子串从 0 位置匹配，并且匹配到最后一个字符才发现不对，白搞)
ssssssssasssa

效率不高

kmp的算法出现，就是为了解决这个问题

kmp是由三位大佬发现的，他们三人的名字首字母分别就是K、M、P

有没有一种办法就是少做无用功，在刚刚那个场景下

先 （a和c不匹配）
ssssssssa
sssa其次，(子串从 2 位置匹配)
ssssssssasssa然后，(子串从 2 位置匹配)
ssssssssasssa.......最后
然后，(子串从 2 位置匹配)，匹配成功
ssssssssasssa

从 2 位置匹配，显然提高了匹配速度

但是 2 位置是怎么知道的呢，kmp 算法中就是先计算一个数组叫做 next，这个next计算只需要子串，然后next的作用是记录子串回溯的位置，当源串和子串不匹配时，不像上面那样老是回溯0

子串      sssa
next数组  0120

回溯的位置就是最长前缀的位置

比如

子串      abcabcd
next数组  ...1230
解释
1 是因为 a=a
2 是因为前面已经有匹配字符 a=a 了，那么 现在刚好 b=b，就最长前缀就等于 1 的基础上加 1 等于 2
3 是因为前面已经有匹配字符 a=a b=b 了，那么 现在刚好 c=c，就最长前缀就等于 2 的基础上加 1 等于 3
0 是因为d没有最长前缀为啥next是基于前缀，因为比如我都匹配到最后一位d和a（源串第七个）不相等了，由于前面有相似的前缀
源串 abcabcaeee
子串 abcabcd那么下一步就是 【子串a（第四个）和a（源串第七个，第七个刚刚没匹配上）比，就是因为前缀一样，才敢让子串匹配位置不从0开始，因为前面有相似的结构】
源串 abcabcaeee
子串    abcabcd特殊场景
子串      sssa
next数组  0120
解释
0 是因为s没有最长前缀
1 是因为 第二个s=第一个s
2 是因为前面已经有匹配字符 s=s 了，那么 现在刚好 第三个s=第二个s，就最长前缀就等于 1 的基础上加 1 等于 2

下面需要结合底部计算next函数一起看

子串      sssa
next数组  0120（其实就是在计算前缀）
计算next数组也是有两个下标计算，建议对照下面代码看 （i为遍历字符串的变量，j为最长前缀的下标）
首先 next[0] 肯定是等于0的，第一个就不匹配，那肯定回溯还是0，
那么 next[1] 由于 str[i] == str[j] 即 str[0] == str[1]，s==s,前缀相同，j自然++
next[1]=j，即 next[1]=1
由于本题是 sssa
所以会出现子串      sssa
next数组  012？（题外话，我们知道a是在前面没有最长前缀的，最后结果肯定为0）
匹配到最后一位时，我们发现跟前面不相等，j就看看前面有没有相等的，j=2，但是 str[2] 也不等于 a
然后while循环一直往前找最长前缀（从2到1到0），最终没找到，为0但是，比如子串      aaaab....aaaaa
next数组  01230....0123?(此时j为3，i为n)?处 a和b不匹配，j=next[j-1]，即 j=next[3-1]，即 j=2,而str[2]==str[n],j++，退出
next[n]=3，这里j没有从0开始，快了一点，其实从0开始也能算出3这个结果最终结果为
子串      aaaab....aaaaa
next数组  01230....01233

上代码

class Solution {
public:int strStr(string haystack, string needle) {// 计算nextvector<int> next(needle.length(), 0);getNext(needle, next);// 匹配过程int j=0;int i=0;for(;i<haystack.length() && j<needle.length();) {// 当前串匹配if (haystack[i]==needle[j]) {j++;i++;} else  {// 当前串不匹配if (j==0)// 防止j一直卡在0，死循环i++;else// 当前串不匹配，但是i的值不自增，只改变j j=next[j-1];}}// 返回结果if (j==needle.length())return i-j;elsereturn -1;}void getNext(string &str,vector<int> &next) {// j 从 0 开始， i 从 1 开始，已知第一个 next[0] 一定是等于 0 的，因为前面没有字符了for(int j=0,i=1;i<str.length();i++) {// 当前如果不匹配，那就去看看它前一个的下标位置对应的字符是否匹配while (j > 0 && str[i] != str[j]) {j=next[j-1];}// 当前如果匹配，j 往前走if(str[i]==str[j]) {j++;}// j 走多远，前缀最长就是多远next[i] = j;}}
};