chuang3.cpp

用历史上有名的KMP模式进行串的模式匹配

//KMP模式匹配算法
#include<stdio.h>
#include<stdlib.h>
//声明串的存储结构
typedef struct{
	char *ch;
	int length;
}HString;
//将chars的值赋于串T
HString StrAssign(HString T,char *chars)
{
	int i,j=0;
	for(i=0;chars[i];++i);
	if(!i) {T.ch=NULL; T.length=0;}
	else {
		if(!(T.ch=(char*)malloc(i*sizeof(char))))
			exit(0);
         for(j=0;j<=i-1;j++)
			 T.ch[j]=chars[j];
		     T.length=i;
			 }
return T;
}
//寻找子串每个元素不匹配时的next值
void get_next(HString T,int *next)
{
	int i=1,j=0;
	next[1]=0;
	while(i<=T.length)
	{
		if(i==1) {++i;++j;next[i]=j;} 
		if(T.ch[i-1]==T.ch[j-1] || j==0) 
		{++i;++j;next[i]=j;}
		else j=next[j];
	}
}
//KMP算法描述
int index_KMP(HString S,HString T,int pos){
	int i=pos-1;
	int j=0;
	int next[100];
	get_next(T,next);
	while(i<S.length && j<=T.length)
	{
		if(i==pos-1) {++i;++j;}
		if(S.ch[i-1]==T.ch[j-1] || j==0) {++i;++j;}
		else j=next[j];
	}
	if(j>T.length) return i-T.length;
	else return 0;
}
void main()
{
	int next[100];
	HString A,B;
	char a[100],b[100];
	int h;
	printf("Please enter a string as a mother string:");
	gets(a);
	printf("Please enter a string as a son string:");
	gets(b);
	printf("Please enter a integer an the start position:");
	scanf("%d",&h);
	A=StrAssign(A,a);
	B=StrAssign(B,b);
	printf("The start position of the son string in the mother string is:%d",index_KMP(A,B,h));
	printf("\n");
    
}