欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

字符串暴力匹配算法

程序员文章站 2022-07-15 18:55:17
...

字符串暴力匹配算法

这里不是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;
}

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

相关标签: 数据结构与算法