数据结构-KMP算法

数据结构-KMP算法

“KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特 *** 作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。” 

这是之前数据结构课的一次实验。代码使用C++编写，可以输出匹配串的过程步骤。

现把代码整理到博客上。

#include
#include
#include
#define MAX 200
#define JMAX 15

typedef struct{
	char Char[MAX];
	int length;
}SString;

void Meum();
int Bulid(SString &s,SString &t);
int Bf(SString s,SString t,int pos);
int Kmp(SString s,SString t,int pos,int *next);
void get_next(SString t,int next[]);
void get_nextval(SString t,int nextval[]);
int Kmpval(SString s,SString t,int pos,int *nextval);
void showNext(SString t,int next[],int nextval[]);

int main(){
	SString s,t;//s为主串 t为模式串
	int x;//x为选择变量 pos为匹配起始位置
	int pos;
	int next[JMAX];
	int nextval[JMAX];
	bool Judge=1;
	while(Judge){
		Meum();//菜单序列
		scanf("%d",&x);
		switch(x){
		case 1:
			pos=Bulid(s,t);
			get_next(t,next);
			get_nextval(t,nextval);
			showNext(t,next,nextval);
			break;
		case 2:
			Bf(s,t,pos);
			showNext(t,next,nextval);
			break;
		case 3:
			Kmp(s,t,pos,next);
			showNext(t,next,nextval);
			break;
		case 4:
			Kmpval(s,t,pos,nextval);
			showNext(t,next,nextval);
			break;
		case 0:
			Judge=0;
			break;
		default:
			break;
		}
	}
	return 0;
}

int Bulid(SString &s,SString &t){
	int pos;
	printf("请输入主串n");
	scanf("%s",s.Char+1);
	printf("请输入模式串n");
	scanf("%s",t.Char+1);
	s.length=strlen(s.Char)-1;
	t.length=strlen(t.Char)-1;
	printf("请输入匹配起始位置n");
	scanf("%d",&pos);
	printf("创建成功n");
	return pos;
}


void get_next(SString t,int next[]){
	int i=1;
    next[i]=0;
	int j=0;
	while(i1){
			for(y=1;yt.length){
		printf("t比较%d次nn",j-1);
		printf("匹配成功，在主串i=%d处位置发现子串n",i-t.length);
		printf("匹配趟数:%d,总字符串比较次数为:%dn",num1-1,num2);
		return(i-t.length);
	}		
	else 
	{printf("匹配失败n");return 0;}
}

int Kmpval(SString s,SString t,int pos,int *next){
	int i,j,pre=0;//
	int x,y,num1=1,num2=0;//x为循环输出变量
	i=pos;
	j=1;
	printf("从主串的第%d个字符开始匹配的结果n",pos);
	printf("主      串:  ");
	for(x=1;x<=s.length;x++)
		printf("%c ",*(s.Char+x));
	printf("n");
	while(i<=s.length && j<=t.length){
		printf("第%d趟匹配 ：",num1);
		if(num1<10)
			printf(" ");
		if(j>1){
			for(y=1;yt.length){
		printf("t比较%d次nn",j-1);
		printf("匹配成功，在主串i=%d处位置发现子串n",i-t.length);
		printf("匹配趟数:%d,总字符串比较次数为:%dn",num1-1,num2);
		return(i-t.length);
	}		
	else 
	{printf("匹配失败n");return 0;}
}

int Bf(SString s,SString t,int pos){
	int i,j,sum=0;//
	int x,num1=1,num2=0;//x为循环输出变量
	i=pos;
	j=1;
	printf("从主串的第%d个字符开始匹配的结果n",pos);
	printf("主     串:  ");
	for(x=1;x<=s.length;x++)
		printf("%c ",*(s.Char+x));
	printf("n");
	while(i<=s.length && j<=t.length){
		printf("第%d趟匹配：",num1);
		if(num1<10)
			printf(" "); 
		for(x=1;xt.length){
		printf("t比较%d次nn",j-1);
		printf("匹配成功，在主串i=%d处位置发现子串n",i-t.length);
		printf("匹配趟数:%d,总字符串比较次数为:%dn",num1-1,(sum+t.length));
		return(i-t.length);
	}		
	else 
	{
		printf("匹配失败n");
		return 0;
	}
}

void Meum(){
	printf("-------------------------------------------------n");
	printf("1. 输入主串、子串和匹配起始位置n");
	printf("2．朴素的模式匹配算法n");
	printf("3．KMP算法n");
	printf("4．KMP改进算法n");
	printf("0. 退出n");
	printf("请输入你的选择n");
	printf("-------------------------------------------------n");
}


void showNext(SString t,int next[],int nextval[]){
			int i;
			printf("模式数组信息n");//输出next nextval数组信息
			printf("-------------------------------------------------n");
			printf("jt");
			for(i=1;i<=t.length;i++)
				printf("%d  ",i);
			printf("n");
			printf("模式串t");
			for(i=1;i<=t.length;i++)
				printf("%c  ",*(t.Char+i));
			printf("n");
			printf("nextt");
			for(i=1;i<=t.length;i++)
				printf("%d  ",next[i]);
			printf("n");
			printf("nextvalt");
			for(i=1;i<=t.length;i++)
				printf("%d  ",nextval[i]);
			printf("n");
}