三默网为您带来有关“暴力求解字符串匹配”的文章内容,供您阅读参考。
暴力求解字符串匹配
2023-01-21 17:18:17
题目
- 给定一个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);
}