字符串暴力匹配算法

字符串暴力匹配算法

这里不是KMP算法,KMP算法等我研究透彻再发出来,,这个只是暴力**,主串需要回溯,而KMP算法的主串是不需要回溯的。
代码如下:

#include<stdio.h>
#include<string.h>
#include<malloc.h>
typedef struct
{
	char *str;         //str指向动态数组的首地址
	int maxLength;   //动态数组字符的最大个数
	int length;       //串的当前长度
}DString;
void Initiate(DString *S,int max,char *string)
{
	int i;
	S->str=(char *)malloc(sizeof(char)*max);   //申请动态数组空间
	S->maxLength=max;
	S->length=strlen(string);               //置串的当前长度值
	for(i=0;i<S->length;i++)
		S->str[i]=string[i];                   //赋值
}
void Destroy(DString *s)
{
	free(s->str);
	s->maxLength=0;
	s->length=0;
}
int BFIndex(DString S,int start,DString T)
{//查找主串S从start开始的子串T,成功则返回T在S中的首字符位置,失败则返回-1
	int i=start,j=0,v;
	while(i<S.length&&j<T.length)
	{
		if(S.str[i]==T.str[j])
		{
			i++;
			j++;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j==T.length)
		v=i-T.length;
	else
		v=-1;
	return v;
}
int main()
{
	DString mystring1,mystring2;
	int max1=29,max2=9;
	int pos=0;
	Initiate(&mystring1,max1,"Data Structure Data Structure");
	Initiate(&mystring2,max2,"Structure");
	//第一次查找
	pos=BFIndex(mystring1,pos,mystring2);
	printf("第一次查找时 pos=%d\n",pos);
	//第二次查找
	pos=BFIndex(mystring1,pos+1,mystring2);
	printf("第二次查找时 pos=%d\n",pos);
	Destroy(&mystring1);
	Destroy(&mystring2);




	return 0;
}

运行结果(这里返回的是第一次出现的下标)
字符串暴力匹配算法

猜你喜欢