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;

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 && 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(&mystr1, str1);
	Initiate(&mystr2, str2);
	printf("\n");
	printstr(&mystr1);
	printf("\n");
	printstr(&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);
}