kmp改进算法.c

几个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 && 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(&mystr1, str1);
	Initiate(&mystr2, str2);
	printf("\n");
	printstr(&mystr1);
	printf(" %d",mystr1.Length);
	printf("\n");
	printstr(&mystr2);
	printf(" %d",mystr2.Length);
	printf("\n");

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