【BF算法】
创始人
2024-05-02 10:44:58
0

BF 算法

  • BF 算法精讲

在学习到字符串的匹配问题时,了解到了BF算法和KMP算法。
对比这两个算法,先了解BF算法;

字符串匹配问题,比如说:有一个主串 “abbbcdef” , 子串 “bbc”,该问题就是在主串中查找子串。

肉眼可见,主串中的确存在子串bbc,返回值是子串在主串中第一次出现的首位置下标,也就是返回2.

BF

首先来看一下下图

在这里插入图片描述
以上面的例子为例:
i指向位置和j所指向位置不相等,那么i就往后移一位
如下图:
在这里插入图片描述
此时i 和 j 所指位置相等,相等,i 和 j 都后移一位。再比较,相等,继续后移,此时到了下图的位置:
在这里插入图片描述
在这个地方不再相等了,所以 j 应该回退到初始位置,那么 i 应该回退到哪里呢 ? 其实很简单, i 和 j 是一起移动的, j 移动了多少位,i 就移动多少位 ,所以 i 回退的位置应该是 i - j +1
i = i - j +1 ,i - j 是 i 和 j 一起移动的长度,再 +1,就是i 从 开始的位置往后移了一位。
如下图:
在这里插入图片描述
从该位置再继续开始匹配, 第一次相同,第二次也相同,第三次也相同,这个过程就是

if (str[i] == sub[j]) str是主串,sub是子串
{i++;j++;
}

当j移动到 '\0’的位置时,表明已经匹配成功,
如下图:

在这里插入图片描述
匹配成功,则返回 子串在主串中第一次出现的起始位置
也就是 return i - j;

到了这里 , BF 算法的核心就结束了

BF算法其实就是一个个地往下匹配,不相等时主串的 i 走到下一位,子串回到初始位置,也就是朴素的匹配算法。

下面看代码:

int BF(const char* str, const char* sub)
{assert(str && sub);int i = 0;//记录主串int j = 0;//记录子串size_t len_dest = strlen(str);//strlen 返回值是size_tsize_t len_src = strlen(sub);if (len_src == 0){return 0;//子串为空,返回主串起始位置}while (iwhile (str[i] == sub[j]){     i++;j++;}if (j >= len_src )// 子串到了'\0'位置了{return i - j;//找到了}//不相等就往下继续匹配i = i - j + 1;j = 0;}//退出该循环,说明找完主串都找不到,不存在该子串return -1;
}int main()
{printf("%d\n", BF("abbbcdef", "bbc"));printf("%d\n", BF("abbbcdef", "bcd"));printf("%d\n", BF("abcdef", ""));return 0;
}

核心部分已做注释:

结果如下:
在这里插入图片描述

相关内容

热门资讯

安卓双系统添加应用,轻松实现多... 你有没有想过,你的安卓手机里可以同时运行两个系统呢?听起来是不是很酷?想象一边是熟悉的安卓系统,一边...
pipo安卓进系统慢,探究pi... 最近是不是发现你的Pipo安卓系统更新或者运行起来特别慢?别急,今天就来给你好好分析分析这个问题,让...
怎样使用安卓手机系统,安卓手机... 你有没有发现,安卓手机已经成为我们生活中不可或缺的一部分呢?从早晨闹钟响起,到晚上睡前刷剧,安卓手机...
双系统安卓安装caj,轻松实现... 你有没有想过,你的安卓手机里装上双系统,是不是就能同时享受安卓和Windows系统的乐趣呢?没错,这...
安卓使用ios系统教程,安卓用... 你是不是也和我一样,对安卓手机上的iOS系统充满了好奇?想要体验一下苹果的优雅和流畅?别急,今天我就...
安卓系统gps快速定位,畅享便... 你有没有遇到过这样的情况:手机里装了各种地图导航软件,但每次出门前都要等上好几分钟才能定位成功,急得...
安卓手机系统更新原理,原理与流... 你有没有发现,你的安卓手机最近是不是总在提醒你更新系统呢?别急,别急,让我来给你揭秘一下安卓手机系统...
安卓系统通知管理,全面解析与优... 你有没有发现,手机里的通知就像是一群调皮的小精灵,时不时地跳出来和你互动?没错,说的就是安卓系统的通...
安卓系统手机哪买,揭秘哪里购买... 你有没有想过,拥有一部安卓系统手机是多么酷的事情呢?想象你可以自由安装各种应用,不受限制地探索各种功...
安卓系统 ipv4,基于安卓系... 你知道吗?在智能手机的世界里,有一个系统可是无人不知、无人不晓,那就是安卓系统。而在这个庞大的安卓家...
目前安卓是什么系统,探索安卓系... 亲爱的读者,你是否曾好奇过,如今安卓系统究竟是什么模样?在这个科技飞速发展的时代,操作系统如同人体的...
安卓6.0系统比5.0,从5.... 你有没有发现,自从手机更新了安卓6.0系统,感觉整个人都清爽了不少呢?没错,今天咱们就来聊聊这个话题...
安卓2.36系统升级,功能革新... 你知道吗?最近安卓系统又来了一次大变身,那就是安卓2.36系统升级!这可不是一个小打小闹的更新,而是...
安卓系统源码怎么打开,并可能需... 你有没有想过,安卓系统的源码就像是一扇神秘的门,隐藏着无数的技术秘密?想要打开这扇门,你得掌握一些小...
安卓8.0系统体验视频,智能革... 你有没有听说安卓8.0系统最近可是火得一塌糊涂啊!作为一个紧跟科技潮流的数码达人,我当然要来给你好好...
宣传系统漫画app安卓,探索安... 亲爱的读者们,你是否曾在某个午后,百无聊赖地打开手机,想要寻找一些轻松愉悦的读物?今天,我要给你介绍...
鸿蒙替换安卓系统吗,开启智能生... 你知道吗?最近科技圈里可是炸开了锅,因为华为的新操作系统鸿蒙系统,据说要大举进军手机市场,替换掉安卓...
手机安卓系统深度清理,解锁手机... 手机里的东西是不是越来越多,感觉就像一个装满了杂物的储物柜?别急,今天就来教你一招——手机安卓系统深...
安卓上的windows系统,融... 你有没有想过,在安卓手机上也能体验到Windows系统的魅力呢?没错,这就是今天我要跟你分享的神奇故...
安卓系统焦点变化事件,Andr... 你知道吗?在安卓系统的世界里,最近发生了一件超级有趣的事情——焦点变化事件。这可不是什么小打小闹,它...