南通免费网站建设,张家界建设网站公司,建设视频网站设计意义,校园文化建设也是很久没有写文章了#xff0c;2.25开了学后#xff0c;就一直忙开学考和四级考#xff0c;好不容易是都过去了。接下来就静下心#xff0c;写一写代码和文章。 最近是看了个速成比赛路线#xff0c;刚把递归看完#xff0c;应该是下一章就会做一个递归总结#xff0c… 也是很久没有写文章了2.25开了学后就一直忙开学考和四级考好不容易是都过去了。接下来就静下心写一写代码和文章。 最近是看了个速成比赛路线刚把递归看完应该是下一章就会做一个递归总结那这一篇就先总结回顾一下bf算法。 正文
bf算法也为暴力算法。其和一般的后面的静态查找和散列表不一样后面的是匹配数字查找的这个是查找字符串的。其为字串的定位操作通常称为串的模式匹配。
例如我们要从S“goodgoole“中找到T”goole“,匹配步骤如下
1.主串S从第一位开始S与T前面的三个字母都匹配成功但S第四个字母是d而T的是g。第一位匹配失败。
2、主串退回到上次匹配的下一位从第二位开始主串S的首字母是o要匹配的T首字母是g匹配失败。
3、主串S第三位开始主串s的首字母是o要匹配的T首字母是g匹配失败。
4、主串S第四位开始主串S首字母是d要匹配的T首字母是g匹配失败。
5.主串S第五位开始S与T6个元素全匹配匹配成功。
简单说就是像两层大循环一样嵌套不停搜索直到找到目的字符串。代码如下
#includestdio.h
#includestdlib.h
#includestring.h#define MAXLEN 255typedef struct
{char str[MAXLEN];int length;
}SSteing;int BF(SSteing a,SSteing b,int pos);//隐藏函数声明后c语言库会默认补充但这样不对链接会出问题 int main (void)
{int start 0; SSteing S,T;printf(请输入主串);scanf(%s,S.str);printf(请输入子串);scanf(%s,T.str);S.length strlen(S.str);T.length strlen(T.str);if(BF(S,T,start)){printf(yes起始位置为%d\n,BF(S,T,start));}else{printf(no\n);}system(pause);return 0;
}int BF(SSteing a,SSteing b,int pos)
{int i pos;int j 0;while (i (a.length-1) j (b.length - 1)){if(b.str[j] a.str[i]){j;i;}else{i i - j 1;j 0;}}if(j (b.length - 1)){return (i - b.length 1);}else{return 0;}
}
