c++经典算法_bfs算法代码实现

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

引言

本文主要介绍了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
则实现过程如下(绿色代表相同,红色代表不同):

a b a c a d b
a c a
此时i = 1,j = 1,匹配失败,则 j 返回 0 ,i 返回 i – j + 1 = 1

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

a b a c a d b
a c a
此时 i = 1,j = 0,匹配失败,则 j 继续返回 0,i 返回 i – j + 1 = 2

a b a c a d b
    a c a
此时匹配成功,i = 4,j = 2,因此我们需要返回匹配的第一个字符下标索引值 即 return i – j   即2

另外,我们再用一张图来举个例子,加深理解  如下:
c++经典算法_bfs算法代码实现
图中的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的数据量过大或者里面的字符比较相似时,由于程序要进行一一比较,所以运算会很多且复杂,效率不高。

今天的文章c++经典算法_bfs算法代码实现分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/58764.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注