【算法——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++;
else
i = next[i];
}
if (i == m)
cout << "找到了:" << j - i;
else
return -1;
return 0;
}