BF算法详解（C语言实现）-创新互联

引言

本文主要介绍了BF算法的主要思想、具体流程、C语言代码实现以及自己对该算法的一些感悟

专注于为中小企业提供网站设计、做网站服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业五大连池免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上千企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。

ps：第一次写博客，如有不妥之地，还望各位大佬指正。

BF算法的介绍 简介

BF算法，即暴力（Brute Force）算法，是普通的模式匹配算法。

主要思想

其主要思想为将目标串S（以下简称S）和模式串T（以下简称T）里的字符一一对比寻找（一般从第一个字符开始），如果相同，则比较下一个字符，如果不同，则从S的第二个字符与T的第一个字符开始比较，以此类推，直至最终得到结果。

如果可以在S中寻找到T，我们返回的是相匹配字符串中第一个字符在S串里的下标索引值；如果找不到，我们通常设置为返回-1。

图解

如： S串为a b a c a d b
      T串为a c a

我们用i来遍历S j来遍历T
则实现过程如下（绿色代表相同，红色代表不同）：

aba c a d b
aca
此时i = 1，j = 1，匹配失败，则 j 返回0，i 返回i - j + 1= 1

ps：注意思考为什么i返回的是 i - j + 1

aba c a d b
 ac a
此时 i = 1，j = 0，匹配失败，则 j 继续返回0，i 返回i - j + 1= 2

a ba c ad b
    a c a
此时匹配成功，i = 4，j = 2，因此我们需要返回匹配的第一个字符下标索引值 即 returni - j  即2

另外，我们再用一张图来举个例子，加深理解  如下：

图中的A串即为我们的T串，B串即为我们的S串。
ps：图片来源于其他博友

时间复杂度

最理想的情况下  该算法的时间复杂度为O(n)  其中n为T串的长度，即一次遍历就在S中找到了T

最坏的情况下  该算法的时间复杂度为O(n*m)  其中 m 和 n
分别为 S 和 T 的长度，即前面每次匹配都不成功，直至到 S 的最后一个字符才与之匹配。

代码复现 相关代码

int BF(char* S, char* T)  //S为主串  T为子串
{if (S == NULL || T == NULL) return -1; //保证 S和 T都不为空
	int s = strlen(S);  //计算S串长度
	int t = strlen(T);  //计算T串长度
	int i = 0;  //主串下标
	int j = 0;  //子串下标
	while (i< s && j< t) {if (S[i] == T[j]) {//对应字符相同
			i++;            //i、j往后移位
			j++;
		}
		else {	i = i - j + 1;   //i返回到 i-j+1 的位置
			j = 0;          
		}
	}
	if (j == t)  return i - j; // j == t 说明子串已经全部遍历 即已经找到与 T相匹配的字符串
	                           // 返回相匹配的第一个字符下标
	return -1;    //没有匹配结果时 返回-1
}

运行结果

找到的情况

int main()
{printf("%d\n", BF("abacadb", "aca")); //可以找到 返回值应该为2
	
	return 0;
}

运行结果

找不到的情况

int main()
{printf("%d\n", BF("abacadb", "abc"));  //找不到  返回-1
	
	return 0;
}

运行结果

算法的自我总结

BF是一种简单暴力的算法，通过将两个字符串内的字符一一比较来得到最终结果。
因为是一种暴力算法，比较无脑，所以实现过程比较简单，逻辑也不难
适合应用于两个数据量较小的串之间的匹配。
但如果两个字符串S和T的数据量过大或者里面的字符比较相似时，由于程序要进行一一比较，所以运算会很多且复杂，效率不高。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站名称：BF算法详解（C语言实现）-创新互联
网站网址：http://6mz.cn/article/shigg.html