草庐IT

BF算法详解（C语言实现）

Iawfy22 2024-05-10 原文

引言

本文主要介绍了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

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

图中的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的数据量过大或者里面的字符比较相似时，由于程序要进行一一比较，所以运算会很多且复杂，效率不高。

详解算法spanclasstokenc语言

有关BF算法详解（C语言实现）的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

  2. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  3. ruby - 寻找通过阅读代码确定编程语言的ruby gem？ - 2

    几个月前，我读了一篇关于ruby​​gem的博客文章，它可以通过阅读代码本身来确定编程语言。对于我的生活，我不记得博客或gem的名称。谷歌搜索“ruby编程语言猜测”及其变体也无济于事。有人碰巧知道相关gem的名称吗？ 最佳答案 是这个吗:http://github.com/chrislo/sourceclassifier/tree/master 关于ruby-寻找通过阅读代码确定编程语言的rubygem？，我们在StackOverflow上找到一个类似的问题：

  4. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

  5. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  6. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  7. 7个大一C语言必学的程序 / C语言经典代码大全 - 2

    嗨~大家好，这里是可莉！今天给大家带来的是7个C语言的经典基础代码~那一起往下看下去把【程序一】打印100到200之间的素数#includeintmain(){ inti; for(i=100;i 【程序二】输出乘法口诀表#includeintmain(){inti;for(i=1;i 【程序三】判断1000年---2000年之间的闰年#includeintmain(){intyear;for(year=1000;year 【程序四】给定两个整形变量的值，将两个值的内容进行交换。这里提供两种方法来进行交换，第一种为创建临时变量来进行交换，第二种是不创建临时变量而直接进行交换。1.创建临时变量来

  8. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  9. MIMO-OFDM无线通信技术及MATLAB实现（1）无线信道：传播和衰落 - 2

     MIMO技术的优缺点优点通过下面三个增益来总体概括：阵列增益。阵列增益是指由于接收机通过对接收信号的相干合并而活得的平均SNR的提高。在发射机不知道信道信息的情况下，MIMO系统可以获得的阵列增益与接收天线数成正比复用增益。在采用空间复用方案的MIMO系统中，可以获得复用增益，即信道容量成倍增加。信道容量的增加与min(Nt,Nr)成正比分集增益。在采用空间分集方案的MIMO系统中，可以获得分集增益，即可靠性性能的改善。分集增益用独立衰落支路数来描述，即分集指数。在使用了空时编码的MIMO系统中，由于接收天线或发射天线之间的间距较远，可认为它们各自的大尺度衰落是相互独立的，因此分布式MIMO

  10. 【Java入门】使用Java实现文件夹的遍历 - 2

    遍历文件夹我们通常是使用递归进行操作，这种方式比较简单，也比较容易理解。本文为大家介绍另一种不使用递归的方式，由于没有使用递归，只用到了循环和集合，所以效率更高一些！一、使用递归遍历文件夹整体思路1、使用File封装初始目录，2、打印这个目录3、获取这个目录下所有的子文件和子目录的数组。4、遍历这个数组，取出每个File对象4-1、如果File是否是一个文件，打印4-2、否则就是一个目录，递归调用代码实现publicclassSearchFile{publicstaticvoidmain(String[]args){//初始目录Filedir=newFile("d:/Dev");Datebeg

随机推荐