#include <iostream>
#include <cstring>
using namespace std;
void KMP_next(const char* str, int* next)
{
int i, j;
i = 1;
j = 0;
next[0] = -1;
while (i < strlen(str))
{
if (j == -1 || str[i] == str[j])
{
if (str[i] == str[j])
next[i] = next[j];
else
next[i] = j;//原始操作...添加上一条判断,只是为了更快的匹配...
i++;
j++;
}
else
{
j = next[j];
}
}
}
int KMP(const char* s, const char* t, int pos, int* next)
{
int i = pos, j = 0;
while (i < strlen(s) && (j == -1 || j < strlen(t)))
{
if (j == -1 || s[i] == t[j])
{
i++;
j++;
}
else
j = next[j];
}
if (j >= strlen(t))
return i - strlen(t);
else
return -1;
}
int main()
{
char* t = "aacasda";
int* next = new int[strlen(t)];
KMP_next(t, next);
for (int i = 0; i < strlen(t); i++)
cout << next[i] << " ";
cout << endl;
cout << KMP("badfaacasdaew", t, 0, next) << endl;
delete [] next;
return 0;
}
KMP.rar_visual c
版权申诉
157 浏览量
2022-09-24
15:13:37
上传
评论
收藏 581B RAR 举报
钱亚锋
- 粉丝: 90
- 资源: 1万+