【算法——KMP】

1理解next数组定义：最长相等前后缀（不含当前字符并且不能是整体）

算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili

next数组的值：假设这个i出现了不匹配就从next[i]的位置开始在再匹配

2next数组生成

 看一下是怎么跳的：算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili

为什么这么跳：算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili

next代码：算法讲解100【扩展】 KMP算法原理和代码详解_哔哩哔哩_bilibili

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;vector<int> fun_next(string str1)    //next生成
{vector<int>next(str1.size());next[0] = -1;next[1] = 0;int i = 2, cn = 0;while (i < str1.size()){if (str1[i - 1] == str1[cn])next[i++] = ++cn;   else if (cn > 0)   //一次不成功，cn还可以往前跳 。cn为0说明没有前后缀，下一个就是0了 cn = next[cn];  else next[i++] = 0;}return next;
}int main()
{string str1("abcabc");string str2("afdfabcabcghj");vector<int>next = fun_next(str1);for (auto i : next)cout << i << " ";cout << endl;int m = str1.size(), n = str2.size();int i = 0, j = 0;while (i < m && j < n)   //匹配{if (str1[i] == str2[j]){i++; j++;}else if (i == 0)j++;elsei = next[i];}if (i == m)cout << "找到了:" << j - i;elsereturn -1;return 0;
}