ITPub博客

首页 > Linux操作系统 > Linux操作系统 > KMP字符串匹配

KMP字符串匹配

原创 Linux操作系统 作者:tyoodz 时间:2012-04-01 11:02:35 0 删除 编辑
#include
using namespace std;

void Get_Next(char* T,int* next);      
void Get_Nextval(char* T,int* next);   
int Index_KMP(char* S,char* T,int* N); 

int main()
{
char S[500];
char T[255];
    int N[255];

cout<<"S:";
cin>>S;
cout<<"T:";
cin>>T;

Get_Next(T,N);
// Get_Nextval(T,N);
for(int i=0;i
{
cout<
}
cout<

//cout<

    return 0;
}


int Index_KMP(char* S,char* T,int* N)
{
int i,j;
i=0;
j=0;
int sl = strlen(S);
int tl = strlen(T);
while(i
{
if(j == -1 ||S[i] == T[j])
{
i++;
j++;
}
else
{
j = N[j];
}
}
if(j==strlen(T))
{
return i-j;
}
else
{
return -1;
}
    
}


void Get_Next(char* T,int* next)
{
int i,j;
i=0;
j=-1;
next[0]=-1;
while(i
{
if(j==-1 || T[i] == T[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}


void Get_Nextval(char* T,int* next)
{
int i,j;
i=0;
j=-1;
next[0]=-1;
while(i
{
if(j==-1 || T[i] == T[j])
{
i++;
j++;
if (T[i] != T[j])
   next[i] = j;
else
                next[i] = next[j];
}
else
{
j = next[j];
}
}
}

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/25361369/viewspace-720121/,如需转载,请注明出处,否则将追究法律责任。

上一篇: 冒泡排序
下一篇: 二叉树遍历
请登录后发表评论 登录
全部评论

注册时间:2011-05-16

  • 博文量
    55
  • 访问量
    74237