三默网为您带来有关“暴力求解字符串匹配”的文章内容,供您阅读参考。

暴力求解字符串匹配

2023-01-21 17:18:17

暴力求解字符串匹配

题目

  1. 给定一个n个字符组成的串(称为文本),一个m(m<.n)个字符组成的串(称为模式),从文本中寻找匹配模式的子串。
    建模:给定两个字符串text和pattern,长度分别为n和m(n>m),判断pattern是否在text中出现,如果出现则返回出现的位置,否则返回-1。

原理:

将模式对准文本的前m个字符从左往右进行比对,如果其中有一个字符不匹配,模式往右移动一位继续下一个m个字符的比对。最坏的情形是模式须移动n-m+1次,每次移动模式之前,做足m次比对才发现不匹配。因此,在最坏情况下,该算法属于Θ(nm)。

基本思想

其算法思想是用两个标志i,j分别记录两个字符串的下标,我们用i表示母串s的下标,j表示子串J的下标,然后从母串的第一个字符与子串的第一个开始,逐一向后寻找,若遍历过程中两个标志所指字符不匹配,则子串标志j置为0,母串标志置为该趟初始位置的后一位即i=i-j+1,当遍历完子串都匹配时,母串标志与子串标志的差值就是所寻找的匹配初始字符的逻辑位置。

代码

include<stdlib.h>
int  BF(char *s,char *p)
{
	int i=0;
	int j=0;
	while((i<strlen(s))&&(j<strlen(p)))
	{
		if(s[i]==p[j])
		{
			++i;
			++j;
		}
		else
		{
			i=i-j+1;
			j=0;
		}
	}
	if(j==strlen(p))
	{
	return i-j+1;
	}
	else
	{
		return -1;
	}
}

int main()
{
	char ar[]="cababceabcdabcede";
	char br[]="abcdabce";
	printf("%d %c\n",BF(ar,br),ar[BF(ar,br)-1]);
	exit(0);
}

总结