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; 

void GetNext(strtype t) { 
/* 求模式串t的next值。所求值存于全局变量数组Next中 */ 
int j, k; 

Next[0]= -1; 
k=-1; j=0; /* 指针初始化 */ 
while(j<t.Length) { 
if(k==-1 || t.Str[j]==t.Str[k]) { 
j++; 
k++; 
Next[j]=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; 
} 

int KMPIndex(strtype s, strtype t) { 
/* 在主串s中定位查找子串t的KMP算法 */ 
int i, j, v; 
i=0;j=0; /* 主串和子串指针初始化 */ 
while(i<s.Length &amt;&amt; j<t.Length) { 
if(j==-1 || s.Str[i]==t.Str[j]) { 
i++; /* 主串和子串指针各增1 */ 
j++; 
} 

else 
j=Next[j]; /* 主串指针i不后退；子串指针j后退到Next[j] */ 
} 
if ( j== t.Length) 
v=i-t.Length; 
else 
v=-1; 
return v; 
} 

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

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

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