BF算法(暴力算法)
BF算法C语言版
·
1. 什么是BF算法呢?
BF算法,即暴力 (Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。 ----百度百科
相信很多人和我一样,看完定义不明白啥意思,下面就来跟大家解释一下:
如图所示:S串为目标串,T串为模式串,我们要再S串中找出T串;如果找到了则返回T串在S串中的起始位置。
找的方法是:从S与T的首个字符开始进行比对,如果二者相等,则比较下一个字符,直到T串的每个字符都比较完,那么就找到了T串在S串中的位置,返回该位置的下标;
如果二者不想等,则T串从头再来,S串回到刚开始位置的下一个位置,再重新进行比对。
那么这个S的新位置应该怎么算呢?如上图所示就应该是2-2+1=1, 也就是i-j+1
经过多次比对后,i j来到了如下位置
又经过一轮比对后,T串走到了末尾。那么此时就已经在S串中找到了T串,就应该返回T串在S串中的起始位置8-3=5,也就是 i-j
如果继续进行比较的话,那么T串会出现下标越界,因此可以将 j<T串长度 作为一个边界条件
2. 代码实现
#include<stdio.h>
#include<string.h>
int BF(const char* S, const char* T)
{
if (S == NULL || T == NULL)
{
return -1;
}
int lenstr = strlen(S);
int lensub = strlen(T);
int i = 0;
int j = 0;
while (i < lenstr && j < lensub)
{
if (S[i] == T[j])
{
i++;
j++;
}
else
{
i = i - j + 1;//S串回到刚开始位置的下一个位置
j = 0; //T串从头再来
}
}
if (j >= lensub) //T串走完了,则找到了
{
return i - j;
}
else
return -1;
}
int main()
{
printf("%d\n", BF("ababcabcdabcde", "abcd"));//5
printf("%d\n", BF("ababcabcdabcde", "abcdd"));//-1
printf("%d\n", BF("ababcabcdabcde", "a"));//0
}
3.算法时间复杂度
- BF 算法执行效率最高的理想情况是第一次模式匹配就成功了,While 循环只执行 n 次(n为模式串的长度),对应的时间复杂度为O(n)。
- BF 算法最坏情况下的时间复杂度为 O(n*m)。举个简单的例子,假设模式串 A 为 “01”,它的长度为 2;主串 B 为 “000000001”,它的长度为 9,两个串模式匹配时,while 循环共执行了 2 * 8 +1 次,近似等于 n * m 次。
4.总结
- BF 算法的实现过程很 “无脑”,不包含任何技巧。实际上,我们可以对 BF 算法的实现过程进行改进,下一节会给大家讲解 BF算法的一个改进版本,称为 KMP 算法。
- KMP算法
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
已为社区贡献1条内容
所有评论(0)