C语言教程-KMP字符串搜索算法

C语言教程-KMP字符串搜索算法

// MyKMP.cpp : Defines the entry point for the console application. 
#include "stdafx.h" 

int next[255]; 
char pat[]="aacaab"; 
char str[]="fsoifhewgsdksdkfhsdifhewhfefksdhfdsoihfoehfosdhfdsaacaab"; 

void getNext(char pat[], int next[]) 
{ 

int j=0; 
for(int i=0;pat[i];i++) 
{ 
if(i==0) next[i]=-1;  
else 
{ 
if(pat[i]==pat[j]) 
{ 
++i; 
++j; 
next[i]=j; 
} 
else j=next[j]; 
} 

} 
} 

int KMP(char *str1, char*pat, int *next) 
{ 
int i=0,j=0; 
while(str[i]) 
{ 
if(pat[j]==0) return i-j; 
if(j==0 || str[i]==pat[j]){ 
++i; 
++j; 
} 
else j=next[j]; 
} 
if(pat[j]==0) return i-j; 
return -1; 
} 

int main(int argc, char* argv[]) 
{ 
int i; 
getNext(pat,next); 
int result=KMP(str,pat,next); 
printf("%s\n",str); 
for(i=0;i<result;i++) printf(" "); 
printf("%s\n",pat); 
printf("at %d\n",result); 
return 0; 
} int next[255]; 
char pat[]="aacaab"; 
char str[]="fsoifhewgsdksdkfhsdifhewhfefksdhfdsoihfoehfosdhfdsaacaab"; 

void getNext(char pat[], int next[]) 
{ 
int i; 
int j=0; 
for(i=0;pat[i];i++) 
{ 
if(i==0) next[i]=-1; 
else 
{ 
if(pat[i]==pat[j]) 
{ 
++i; 
++j; 
next[i]=j; 
} 
else j=next[j]; 
} 

} 
} 

int KMP(char *str, char*pat, int *next) 
{ 
int i=0,j=0; 
while(str[i]) 
{ 
if(pat[j]==0) return i-j; 
if(j==0 || str[i]==pat[j]){ 
++i; 
++j; 
} 
else j=next[j]; 
} 
if(pat[j]==0) return i-j; 
return -1; 
} 

int main(int argc, char* argv[]) 
{ 
int i; 
int result; 
getNext(pat,next); 
result=KMP(str,pat,next); 
printf("%s\n",str); 
for(i=0;i<result;i++) printf(" "); 
printf("%s\n",pat); 
printf("at %d\n",result); 
return 0; 
} /*KMP算法*/ 

/*a string begins with index of 0 and ends with the char '\0'*/ 
void getNext(char pat[], int next[])  
{  
int j = 0; 
int k = -1; 
next[0] = -1; 

while (pat[j]) 
{ 
if ( k == -1 || pat[j] == pat[k]) 
{ 
j++; 
k++; 
next[j] = k; 
} 
else 
{ 
k = next[k]; 
} 
}
}  


int index_KMP(char str[], char pat[]) 
{ 
int i = 0; 
int j = 0; 
int next[255]; 

getNext(pat, next); 

while (str[i]) 
{ 
if (pat[j] == '\0') 
{ 
return (i - j); 
} 
if (j == -1 || str[i] == pat[j]) 
{ 
i++; 
j++; 
} 
else 
{ 
j = next[j]; 
} 
} 
return -1; 
}

进入C语言程序设计视频教程专区