谁有KMP算法的C语言实现啊

如题所述

#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
void getNext(const char * t,int * Next)//get the Next array
{
int k=-1;
int j=0;
int size=strlen(t);
Next[0]=-1;
while(j<size)
{
if(k==-1||t[j]==t[k])//if k==-1 there are two conditions
//one is this is the first time entering the loop
{ //if t[j]==t[k] get the next[j+1] directly
k++;//the other is the end of the iteration cos k==-1;
j++;
Next[j]=k;//whatever Next[j]=k
}
else
k=Next[k];
}
}
int myStrstr(const char * Dest,const char *subStr)//find the starting position of the sub
{ //in the Dest through KMP
int destSize=strlen(Dest);
int subSize=strlen(subStr);
int i,j;
int * Next=(int *)(malloc(sizeof(int)*subSize));
i=j=0;
assert((Dest!=NULL)&&(subStr!=NULL));
getNext(subStr,Next);
while(i<destSize&&j<subSize)
{
if(j==-1||Dest[i]==subStr[j])//if j==-1 the main string need match the next elements
{ //and the subString begin from the beginning
i++; //if Dest[i]==subStr[j] both string need shift to the
j++; // next elements
}
else
j=Next[j]; //if match fail,glide back to Next[j]
}
if(j==subSize)return i-j;
return -1;
}
int main()
{
char *temp,*sub,* Dest;//to store the substring to be matched
int ch;
unsigned int templen,length=20*sizeof(char);
unsigned int mlength=20*sizeof(char);//the original length of the memory
sub=(char*)malloc(length);
Dest=(char*)malloc(length);
if(sub==NULL||Dest==NULL)//allocation failure
{
printf("memory allocate failure\n");
exit(0);
}
temp=sub;
printf("please input the substring:\n");
while((ch=getchar())!=10)//read the sub String
{
if((temp-sub)/sizeof(char)==length)//if running out of the memory
{
templen=length;
sub=realloc(sub,length+=20*sizeof(char));
if(sub==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=sub+templen*sizeof(char);//reset the temp cos the sub may change its value
}
*temp++=ch;
}
*temp='\0';
temp=Dest;
printf("please input the mainstring:\n");
while((ch=getchar())!=10)//read the main String
{
if((temp-Dest)/sizeof(char)==mlength)
{
templen=mlength;
Dest=realloc(Dest,mlength+=20*sizeof(char));//if running out of the memory
if(Dest==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=Dest+templen*sizeof(char);//reset the temp cos the Dest may change its value
}
*temp++=ch;
}
*temp='\0';
printf("the starting position is :%d\n",myStrstr(Dest,sub));//get the starting position
free(Dest);
free(sub);
return 0;
}

温馨提示：内容为网友见解，仅供参考

当前网址：https://11.t2y.org/zz/2q7fq47p.html