#include <iostream>
using namespace std;
/**
* paramter pat:待匹配的字符串
* T: 返回的table
*
**/
void kmp_table(const char * W, int T[])
{
int pos = 2; //当前查找的位置
int cnd = 0; //当前查找的前缀字串的位置
T[0] = -1;
T[1] = 0;
while(pos < strlen(W))
{
if( W[cnd] == W[pos-1] )
{
T[pos] = cnd + 1;
pos++;
cnd++;
}
else if( cnd > 0 )
cnd = T[cnd]; //回退,有难度
else
{
T[pos] = 0;
++pos;
}
}
}
int kmp_search(const char * S,const char * W)
{
int m = 0 ; //开始匹配的位置
int i = 0 ; //W中位置
int * T = new int[strlen(W)];
kmp_table(W,T);
for(int j = 0; j < strlen(W); j++)
{
cout << T[j] <<" ";
}
cout<<endl;
while( (m + i) < strlen(S))
{
if(S[m+i] == W[i])
{
++i;
if(i == strlen(W))
return m;
}
else
{
m = m + i - T[i];
if( i > 0) i = T[i];
}
}
}
int main()
{
char * S = "acabaabaabcacaabc";
char * W = "abaabcac";
int p = kmp_search(S,W);
cout<<"p = "<< p <<endl;
}
分享到:
相关推荐
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
KMP算法
KMP算法实现的C++代码,KMP算法实现的C++代码,KMP算法实现的C++代码
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
简单的kmp算法实现,代码结构十分清晰,适合初学者理解kmp算法
KMP算法实现,用Java语言实现的KMP字符串匹配算法
数据结构课程设计,用KMP算法实现的文本检索,检索本地文件,使用MFC,可视化界面
JAVA实现KMP算法,使用java语言实现的kmp算法
模式匹配中的KMP算法的c语言实现及简单的应用介绍!
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
C++实现kmp字符串匹配算法,算法思想: *KMP算法的思想就是在匹配过程称若发生不匹配的情况 *如果next[j]>=0则目标串的指针i不变将模式串的指针j移动到next[j]的位置继续进行匹配 *若next[j]=-1则将...
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家