chuang2.cpp

子串的一般匹配方法

//子串的一般匹配方法
#include<stdio.h>
#include<stdlib.h>
#define MAXSTRLEN 255
//声明串的存储结构
typedef struct{
	char *ch;
	int length;
}HString;
//用一字符数组初始化串
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;
}
//求串的长度
int StrLenghth(HString *S)
{
	return S->length;
}
int Index(HString S,HString T,int pos)
{
	int i,j;
    i=pos-1;
	j=0;
	while(i<S.length && j<T.length){
		if(S.ch[i]==T.ch[j]) {++i;++j;}
		else {i=i-j+2;j=1;}
	}
	if(j>=T.length) return i-T.length+1;
	else return 0;
}
void main()
{
	char a[100],b[100];
	HString a1,b1;
	int c,d;
	printf("Finding the start position of the son string in the mother string!\n");
	printf("Please put in the mother string:");
	gets(a);
	printf("Please put in the son string:");
	gets(b);
	printf("Please enter the start position:");
	scanf("%d",&d);
    a1=StrAssign(a1,a);
	b1=StrAssign(b1,b);
    c=Index(a1,b1,d);
	if(c==0)
	{
		printf("Havn't found the son string!\n");
	    printf("\n");
	}
		else 
	{printf("the start position of the son string in mother string is:%d",c);
     printf("\n");
	}
}