本文主要是介绍KMP 算法模板，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
其实kmp的思想还是很好理解的，就是代码不太好实现，看别人的模板才写出来。。/*kmp 模板 2014年10月18日*/
#include<iostream>
using namespace std;
int f[100];
void getFail(char* p, int* f)//预处理子串
{
int m = strlen(p);
f[0] = 0;
f[1] = 0;
for (int i = 1; i < m; i++)
{
int j = f[i];
while (j && p[i] != p[j])
{
j = f[j];//进行回溯
}
f[i + 1] = p[i] == p[j] ? j + 1 : 0;//记录未匹配的下标 处理到 i+1位
}
}
int find(char* t, char*p, int*f)//匹配
{
int n = strlen(t), m = strlen(p);
getFail(p, f);
int j = 0;
for (int i = 0; i < n; i++)
{
while (j && p[j] != t[i])
{
j = f[j];//回溯
}
if (p[j] == t[i])
{
j++;
}
if (j == m)
{
return i - m + 1;//返回当前位置
}
}
return -1;
}
int main()
{
char *p = "abcabcdda";
char *t = "babdabcabcabcddaaaa";
if(find(t,p, f)==-1)
{
cout << "No" << endl;
}
else cout << "Yes"<<"位置为"<<find(t,p,f) << endl;
return 0;
}
这篇关于KMP 算法模板的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
