【算法——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;
}

原文地址：https://blog.csdn.net/2301_76758064/article/details/142465306

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！