C语言数据结构 BF + KMP 的简洁化代码

说到字符串匹配，这是一个老但是热度不减的话题

也是学数据结构必须要会的

代码--如果不写注释几乎不会有人看

虽然是学计算机的前方的路对我来说还比较迷茫

只能是---》漫天撒网抓蝴蝶---low漏陋

经过半个小时的复习整理想着能将代码简洁化又不失条理

将KMP和BF的写在一起就当做个比较吧

这种经典算法不需要解释至于将代码简洁化

我想大概人人都想自己做而且自己做出来的才有意义别人做的除非很好否则很难看的下去

另外做的字符串替换链接:字符串替换-循环

# include <stdio.h>
# include <stdlib.h>
# define N 101 //用户输入的字符串长度最大值为N-1  第N个存'\0'
# define M 2   //用户输入的字符串长度最小值 
int BF(char a[],char b[]);//BF算法 a为主串,b为被检验的串返回匹配的下标 若无返回0
int KMP(char *A,char *B);//比BF复杂度低  和BF功能相同
int gainchar(char *a,int min,int max);//模拟strlen类 对*a输入范围[min,max-1]返回字符串长度，不影响下一级输入
int main(){
	char A[N],B[N];
	int len;
	PRintf("请输入A字符串(%d---%3d):\n",M,N-1);
	len=gainchar(A,M,N);
    printf("请输入B字符串(%d---%3d):\n",1,len);
	gainchar(B,1,len+1);
    printf("注:匹配失败返回0!\n\n主串:%s\n次串:%s\nBF:匹配的位置:%d\nKMP匹配的位置:%d",A,B,BF(A,B),KMP(A,B));
	return 0;
}
int gainchar(char *a,int min,int max)//对*a输入范围[min,max-1]  防止数组超界 并清除缓冲区
{
	int c,k;
	do{
		c=-1;k=0;
		fgets(a,max,stdin);
		while(a[++c]);
		c=a[c-1]=='\n'&&c<max?c-1:c;
		if(c>=max-1)
			while(getchar()!='\n')
				k++;
			else
				a[c]='\0';
			if(k||c&&(c>max||c<min))//如果用户只输入'\n'则不提示输入错误，否则提示错误
				printf("输入长度有误,请重新输入!\n注:只录入(%d--%d)字节:\n",min,max-1);
	}while(k||c<min);
    return c;
}
int KMP(char *A,char *B)//经典算法  已经简洁化 复杂度 o(strlen(A)+strlen(B))
{                     
	int i=1,j=0,C=-1,*Q=NULL; 
	while(B[++C]); //求主串A的长度
	Q=(int *)calloc(C,sizeof(int));//申请内存存NEXVAL的值
    while(i<C)               //获得模式串的NEXTVAL数组
		if(!j||B[i]==B[j])       
		{
			++j;
			++i;
			Q[i]=(B[i]-B[j]?j:Q[j]);   
		}
		else
			j=Q[j];
		i=j=0;           //开始和主串匹配
		while (A[i]&&B[j])
			if (A[i++]==B[j])
				j++;
			else
				j=Q[j];
	return B[j]?0:i-j+1;    //返回下标值
}
int BF(char a[],char b[])//BF算法 一般o(strlen(A)+strlen(B))  最坏o(strlen(A)*strlen(B))
{                     
	int i=0,j=0; 
	while (a[i]&&b[j])
		if (a[i++]==b[j]) // 如果匹配成功 继续比较后继字
			++j;
		else      //否则 主串回溯
		{
			i-=j;       
			j=0;
		}
	return b[j]?0:i-j+1;  //返回下标 
}路还很长  我还在继续 加油!

C语言数据结构 BF + KMP 的简洁化代码

相关推荐