1. 概述

Kmp算法的介绍及思想参阅下面两篇文章：
字符串匹配KMP算法
算法）通俗易懂的字符串匹配KMP算法及求next值算法

2. 代码实现

int cTest::findstr1(const char *src, const char *des)
{
int srlen = strlen(src);
int delen = strlen(des);
int i = 0, j = 0, k = 0;
for (int i = 0; i <= srlen - delen; i++)
{
/* code */
for (k = i, j = 0; j < delen; ++k, ++j)
{
/* code */
if (src[k] != des[j])
break;
}
if (j >= delen)
return i;
}
return -1;
}
void cTest::subNext_kmp(const char *des, int *next)
{
next[0] = -1;
int i = 0, k = -1;
while (des[i] != '')
{
/* code */
if (k == -1 || des[k] == des[i])
next[++i] = ++k;
else
k = next[k];
}
}
int cTest::findstr2(const char *src, const char *des, int* next)
{
int slen = strlen(src);
int dlen = strlen(des);
int i = 0, j = 0;
while (i < slen && j < dlen)
{
/* code */
if (j==-1 || src[i] == des[j])
{
++i;
++j;
}
else
/* code */
j = next[j];
}
if (des[j] == '')
return i - j;
return -1;
}

3. 代码测试

int main(int argc, char* argv[])
{
char s[] = "abcabaaaabaabcac";
char p[] = "abaabcac";
cout << ctestptr.findstr1(s, p) << endl;
//shared_ptr<int> next(new int[sizeof(p)],[](int* p){delete[] p;});
int *next = (int *)malloc(sizeof(int) * sizeof(p));
ctestptr.subNext_kmp(p, next);
for (int i = 0; i < strlen(p); ++i)
cout << next[i];
cout << endl;
cout << ctestptr.findstr2(s, p, next) << endl;
free(next);
}

最后

以上就是清新小馒头为你收集整理的C++实现字符串匹配KMP算法1. 概述2. 代码实现3. 代码测试的全部内容，希望文章能够帮你解决C++实现字符串匹配KMP算法1. 概述2. 代码实现3. 代码测试所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。