kmp

哈~~早在考研之前就想着等考完之后要把这段时间我编的这些程序都发到我的网站里~~现在终于有时间啦~~

 

首先是kmp算法的~~对了,我觉得以后有时间要多编写一些这种模版类的程序,都保存下来,这样以后用着方便·~

 

 

//kmp.h

template

void nextone(T str[],int next[],int i,int j)    //找相同+1

{

if(i==0) next[i]=-1;

else if(i==1) next[i]=0;

else if(str[i-1]==str[next[j]]) next[i]=next[j]+1;

else if(next[j]==0) next[i]=0;

else nextone(str,next,i,next[j]);

}

 

template

void Next(T str[],int next[],int n)   //n为字符串长度

{

for (int t=0;t<n;t++) nextone(str,next,t,t-1);

}

 

template

void nextvalone(T str[],int next[],int nextval[],int i,int j)  //找不同

{

if(i==0) nextval[i]=-1;

else if(i==1) {if(str[i]==str[i-1]) nextval[i]=-1;

else nextval[i]=0;}

else if(str[i]!=str[next[j]]) nextval[i]=next[j];

else if(next[j]==0) nextval[i]=-1;

else nextvalone(str,next,nextval,i,next[j]);

}

 

template

void NextVal(T str[],int next[],int nextval[],int n)   //n为字符串长度

{

for (int t=0;t<n;t++) nextvalone(str,next,nextval,t,t);

}

 

template

void PrintStr(T str[],int n)

{

for (int i=0;i<n;i++) std::cout<<std::setw(4)<<str[i];

std::cout<<std::endl;

}

 

template

void Fail(T str,int f[],int n) //书P64失败算法

{

int j=0,k=-1;

f[0]=-1;

while(j<n)

{

if((k==-1) || (str[j]==str[k]))

{

j++;k++;

f[j]=k;

}

else k=f[k];

}

}

 

template

void FFail(T str,int f[],int n)  //书P65改进失败函数算法

{

int j=0,k=-1;f[0]=-1;

while(j<n)

{

if((k==-1) || (str[j]==str[k]))

{

j++;k++;

if(str[j]==str[k]) f[j]=f[k];

else f[j]=k;

}

else k=f[k];

}

}

 

template <class T>
int FindKMP(T S,T P,int f[]){   //书P63KMP比较算法
int n,m;n=S.size();m=P.size();
int i=0,j=0;
while(i<n && j<m){
if(j==-1 || S[i]==P[j]){i++;j++;}
else j=f[j];
}
return ((j==m)?i-m:-1);
}

 

 

 

 

 

 

 

然后,干脆把main函数中如何调用的也发上来吧,做个参考~~

#include

#include

#include

#include “kmp.h”

 

using namespace std;

 

int main()

{

/*

char test[]={‘a’,’b’,’c’,’a’,’b’,’c’,’a’,’b’,’b’,’a’,’c’};

int n=11;

int next[11],nextval[11],nextf[11],nextff[11];

*/

/*

char test[]={‘c’,’d’,’d’,’c’,’d’,’e’,’c’,’e’,’c’,’d’,’e’,’a’};

int n=12;

int next[12],nextval[12],nextf[12],nextff[12];

*/

char test[]={‘a’,’b’,’c’,’d’,’a’,’b’,’d’};

int n=7;

int next[7],nextval[7],nextf[7],nextff[7];

 

PrintStr(test,n);

 

Next(test,next,n);

PrintStr(next,n);

 

Fail(test,nextf,n);

PrintStr(nextf,n);

 

NextVal(test,next,nextval,n);

PrintStr(nextval,n);

 

FFail(test,nextff,n);

PrintStr(nextff,n);

}

kmp》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注