gc_8_12.c

gc:高级程序员考试用书的c程序源文件

# include <stdio.h>
# include <string.h>
# include <stdlib.h>
/*简单模式匹配算法*/
int simple_match(char *t,char *p,int *pt)
{
	int n = strlen(t), m = strlen(p),i,j,k;
	for(j=0; j<n-m; j++) {           /*顺序考察从t[i]开始的子串*/
		/*从t[j]开始的子串与字符串p比较*/
		for(i=0;i<m && t[j+i] == p[i]; i++);
		if(i == m) {
	   		 *pt = j;
			 return 1;        /*匹配成功*/
		}
	}
	return 0;                      /*匹配失败*/
}



/*函数,寻找模式各字符失败链接值的函数*/
void faillink(char *p,int next[])
{
	int j,k;
	next[0] = -1; j= 1;
	do {
		k = next[j-1];
		while(k!=-1 && p[k] != p[j-1])
			k = next[k];
		next[j++] = k+1;
	} while(p[j] != '\0');
}

/*函数,KMP模式匹配函数*/
int kmp_match(char *t,char *p,int next[])
{
	int k,j;
	if(*t == '\0') return 0;
	for(k = j = 0; t[k] != '\0';) {
		while(j != -1 && p[j] != t[k])
			j = next[j];
		k++; j++;
		if(p[j] == '\0')
			return k-j;
	}
	return -1;
}


void main()
{
	char t[20],p[10];
	int pt=0;                    /*函数返回匹配开始的位置*/
	int m=0;                 /*模式字符串的长度*/
	int kmp=0;                       /*KMP函数的返回值*/
	int *next;                         /*存储数组,存储失败链接值*,书上是数组*/

	printf("输入长正文字符串t,,找出与模式字符串相同子串的过程称为模式匹配\n");
	printf("请输入长正文字符串,最长19个字符,中间不要有空格,因为用的是scanf函数\n");
	scanf("%s",t);
	printf("请输入模式字符串,最长9个字穃n");
	scanf("%s",p);
	printf("用简单模式匹配算法结果如下:\n");
	if(simple_match(t,p,&pt)) {
		printf("匹配成功\n");
		printf("开始位置为第%d个字符\n",pt);
	}
	else printf("匹配失败\n");

	printf("\n用KMP模式匹配函数,查找模式字符串: \n");
	m=strlen(p);

	next = (int *)malloc(sizeof(int)*m) ;         //由于必须是一个常数值 M
	faillink(p,next);
	if (kmp=kmp_match(t,p,next)) printf("返回值%d\n",kmp);
}