kmp改进算法.c.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

www.pudn.com > algorithm > KMP改进算法.c


#define MAXNUM 80 
#define NULL '\0' 
#define true 1 
#define false 0 

int Next[MAXNUM]; 

typedef struct { 
char Str[MAXNUM]; 
int Length; 
} strtype; 

/* 求模式串t的next值。所求值存于全局变量数组Next中 */ 
void GetNextVal(strtype * str) { 
int k=-1, j=0; 
Next[0]=-1; 

while(j<str->Length) { 
if(k==-1 || str->Str[k]==str->Str[j]) { 
k++; j++; 
if(str->Str[k]!=str->Str[j]) 
Next[j]=k; 
else 
Next[j]=Next[k]; 
} else 
k=Next[k]; 
} 
} 

void Initiate(strtype * s, char * t) { 
int i=0; 
while(t[i]!='\0') { 
s->Str[i] = t[i]; 
i++; 
} 
s->Str[i]='\0'; 
s->Length = i; 
} 

int printstr(strtype * s) { 
printf(">s", s->Str); 
return 1; 
} 


/* 在主串s中定位查找子串t的KMP改进算法 */ 
int KMPIndex(strtype * str1, strtype * str2) { 
int i=0, j=0; 
while(i<str1->Length &amt;&amt; j<str2->Length) { 
printf(" * "); 
if(j==-1 || str1->Str[i]==str2->Str[j]) { 
i++; 
j++; 
printf("- >d -",j); 
} else 
j=Next[j]; 

} 

if(j==str2->Length) 
return i-j; 
else 
return -1; 
} 

main() { 
char * str1="sdfdsfefdabdabdkfjsalkjfdsfjsodijf"; 
char * str2="abdabd"; 
int i=0; 
strtype mystr1, mystr2; 

clrscr(); 
Initiate(&amt;mystr1, str1); 
Initiate(&amt;mystr2, str2); 
printf("\n"); 
printstr(&amt;mystr1); 
printf(" >d",mystr1.Length); 
printf("\n"); 
printstr(&amt;mystr2); 
printf(" >d",mystr2.Length); 
printf("\n"); 

GetNextVal(&amt;mystr2); 
for(i=0;i<mystr2.Length;i++) 
printf(">d ",Next[i]); 
printf("\n"); 
i = KMPIndex(&amt;mystr1, &amt;mystr2); 
printf("\n i is : >d", i); 
}