kmp算法c++
kmp算法通过next数组使查找失败时减少跳转后比较的次数来优化字符串查找，next数组存储了前缀和后缀相同的位置信息，雷同动规，可以存储查找数组的信息来防止重复查找，最终复杂度可以达到O（n+m）。以t=“abcabd”字符串为例进行讲解
next数组存储的是当前位置与前面具有相同前缀的长度，同时在查找失败后，可以在失败位置的其哪一个位置对应的next数组值来跳转到具有相同前缀的字符串的下一个位置，如许就可以制止重复验证前缀部门是否和被查找的字符串匹配。
具体的演示可以看和手算方法见「六分钟速通」KMP算法求解流程，up讲的简单明白。视频里pm即为文中的next数组
next里的数字代表包括t在内的部门与前面字符串部门子串相同的长度，同时该数字也是前面相同子串的下一个字符的下标。
这里设j，k作为下标表示，j为当前盘算的下标，k为前面与当前盘算下标j结尾的子串相同的子串的结尾下标，即具有相同前缀的子串结尾下标。
当k=0时，有两种情况，一是t=t,那么此时next=next+1，即相同前缀部门变大，如果差别，此时k=0，则next应该为0，即没有相同前缀。
当k!=0时，如果t=t,则按上述盘算方法来表示扩大相同前缀，如果t!=t，那么向前找相同前缀，做法时k=next,因为next数组存储的是当前位置与前面具有相同前缀的长度，则向前查找只必要找到以k-1结尾的相同子串的长度，如果还差别，重复向前查找，直到k=0或找到相同前缀为止。
#include <iostream>
#include <string.h>
#include <stdlib.h>
using namespace std;
void grtnext(char *c, int *nextKMP)
{
int len = strlen(c);
nextKMP = 0;
int k = 0;
int j = 1;
while (j < len)
{
if (k == 0)
{
if (c == c)
{
nextKMP = 1;
k++;
}
else
nextKMP = 0;
j++;
continue;
}
if (c == c)
{
nextKMP = nextKMP + 1;
k++;
j++;
}
else
{
k = nextKMP;
}
}
}
int KMP(char *s, char *t, int *next, int *re)
{
int lens = strlen(s);
int lent = strlen(t);
int i = 0, j = 0;
while (i < lens && j < lent)
{
re++;
if (s == t)
{
i++;
j++;
}
else
{
if (j == 0)
i++;
else
j = next;
}
}
if (j == lent)
return i - lent;
return -1;
}
int trlen(char *s)
{
int len = 0;
while (s != '\0')
{
len++;
}
}
int main()
{
char *c = "aabaac";
char *s = "aabaabaaac";
int len = strlen(c);
int re = {0};
int *nextKMP = new int;
grtnext(c, nextKMP);
int k = KMP(s, c, nextKMP, re);
// for (int i = 0; i < len; i++)
// {
// cout << nextKMP << " ";
// }
if(k==-1)cout<<"no find"<<endl;
else
cout << k + 1 << endl;
cout << re; // 输出比较次数
system("pause");
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]