Posted on 2008-08-26 16:48
dengbo 阅读(352)
评论(0) 编辑 收藏 引用 所属分类:
Data Struct
#include "stdafx.h"
#include <iostream>
using namespace std;
int KMP_Search(const char *,const char*,const int *);
void getNext(const char*,int*);
int _tmain(int argc, _TCHAR* argv[])
{
char S[50]="ABC ABCDAB ABCDABCDABDE";
char W[10]="ABCDABD";
int next[10];
getNext(W,next);
int m = KMP_Search(W,S,next);
cout<<m<<endl;
system("pause");
return 0;
}
int KMP_Search(const char *W,const char*S,const int * next)
{
int m=0,i=0,wlen = strlen(W);
while(m+i<strlen(S))
{
if(W[i] == S[m+i])
{ i++;
if(i==wlen)
return m;
}
else
{
m=m + i - next[i];
if (i>0)
i=next[i];
}
}
}
void getNext(const char* S,int next[])
{
int pos=2,cnd=0;
next[0]= -1;
next[1] = 0;
while(pos<strlen(S))
{
if(S[pos-1] == S[cnd])
{
next[pos] = cnd+1;
pos++;
cnd++;
}
if(S[pos-1] != S[cnd] && cnd>0)
cnd = next[cnd];
if (cnd == 0)
{
next[pos] = 0;
pos++;
}
}
}