BF算法详解(JAVA语言实现)
目录
BF算法的介绍
图解
JAVA语言实现
BF算法的时间复杂度
BF算法的介绍
BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继续比较S的第二个字符和 T的第二个字符;若不相等,则比较S的第二个字符和T的第一个字符,依次比较下去,直到得出最后的匹配结果。BF算法是一种蛮力算法。
如果可以在S中寻找到T,我们返回的是相匹配字符串中第一个字符在S串里的下标索引值;如果找不到,我们通常设置为返回-1。
图解
我们用i来遍历S, j来遍历T
则实现过程如下:
(1)i=0,j=0
aabcda
da
匹配失败,则 j 赋值 0 ,i 赋值 i - j + 1 = 1
(2)i=1,j=0
aabcda
da
匹配失败,则 j 赋值 0 ,i 赋值 i - j + 1 = 2
(3)i=2,j=0和i=3,j=0同理 匹配失败
(4)i=4,j=0
aabcda
da
匹配成功,则 i++,j++
(5)i=5,j=1
aabcda
da
匹配成功,返回的是相匹配字符串中第一个字符在S串里的下标索引值,4
JAVA语言实现
public class BF {public static int bf(String str,String sub){if(str==null||sub==null){return -1;}int strlen=str.length();int sublen=sub.length();if(strlen==0||sublen==0){return -1;}int i=0,j=0;while (i<strlen&&j<sublen){if(str.charAt(i)==sub.charAt(j)){i++;j++;}else {i=i-j+1;j=0;}}if(j>=sublen){return i-j;}return -1;}
}
测试:
public static void main(String[] args) {System.out.println(bf("aabcda","da"));}
结果:4
BF算法的时间复杂度
(1)最理想的情况下 该算法的时间复杂度为O(n) 其中n为T串的长度,即一次遍历就在S中找到了T
(2)最坏的情况下 该算法的时间复杂度为O(n*m) 其中 m 和 n
分别为 S 和 T 的长度,即前面每次匹配都不成功,直至到 S 的最后一个字符才与之匹配。
以上为我个人的小分享,如有问题,欢迎讨论!!!
都看到这了,不如关注一下,给个免费的赞
相关文章:

BF算法详解(JAVA语言实现)
目录 BF算法的介绍 图解 JAVA语言实现 BF算法的时间复杂度 BF算法的介绍 BF算法,即暴力(Brute Force)算法,是普通的模式匹配算法,BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配,若相等,则继…...

零基础转行网络工程师,过来人给的一些建议
最近收到好多同学的一些提问,零基础没经验,能不能转行到网络工程师?薪资能有多少?发展前景怎么样? 应该有不少朋友都有这个疑问,那么,今天我尽量给大家做出一个详细的解答,希望能有…...

Vue中如何进行分布式搜索与全文搜索(如Elasticsearch)
在Vue中实现分布式搜索与全文搜索(使用Elasticsearch) 分布式搜索和全文搜索在现代应用程序中变得越来越重要,因为它们可以帮助用户快速查找和检索大量数据。Elasticsearch是一种强大的分布式搜索引擎,它可以用于实现高性能的全文…...

数据结构-图-最小生成树问题
最小生成树 并查集定义举例说明查找某个元素属于哪个集合代码实现路径压缩 Kruskal算法原理代码实现 Prim算法原理代码实现 并查集 定义 🚀在一些应用问题中,需要将n个不同的元素分成一些不相交的集合。开始时,每个元素自成一个单元素集合&…...

使用vite+npm封装组件库并发布到npm仓库
组件库背景:使用elementplusvue封装了一个通过表单组件。通过JSX对el-form下的el-input和el-button等表单进行统一封装,最后达到,通过数据即可一键生成页面表单的功能。 1.使用vite创建vue项目 npm create vitelatest elementplus-auto-form…...

85.最大矩形
单调栈,时间复杂度o(mn),空间复杂度o(mn) class Solution { public:int maximalRectangle(vector<vector<char>>& matrix) {int mmatrix.size();if(m0){return 0;}int nmatrix[0].size();//记录矩阵中每个元素左边连续1的数量vector<…...

Windows服务器 开机自启动服务
1、新建txt,并粘贴下面脚本 start cmd /k "cd /d D:\ahjd&&java -jar clips-admin.jar" start cmd /k "cd /d D:\ahjd\dist&&simple-http-server.exe -i -p 8000"说明,脚本格式为:start cmd /k “cd /d…...
《算法通关之路》chapter17一些通用解题模板
《算法通关之路》学习笔记,记录一下自己的刷题过程,详细的内容请大家购买作者的书籍查阅。 1 二分法 1.1 普通二分法 # 查找nums数组中元素值为target的下标。如果不存在,则返回-1def bs(nums: list[int], target: int) -> int :l, h …...

常用求解器安装
1 建模语言pyomo Pyomo是一个Python建模语言,用于数学优化建模。它可以与不同的求解器(如Gurobi,CPLEX,GLPK,SCIP等)集成使用,以求解各种数学优化问题。可以使用Pyomo建立数学优化模型…...
第三章:最新版零基础学习 PYTHON 教程(第一节 - Python 运算符)
在Python编程中,运算符一般用于对值和变量进行操作。这些是用于逻辑和算术运算的标准符号。在本文中,我们将研究不同类型的Python 运算符。 运算符:这些是特殊符号。例如- + 、 * 、 / 等。操作数:它是应用运算符的值。目录 Python 中的运算符类型 Python 中的算术运算符…...

细粒度特征提取和定位用于目标检测:PPCNN
1、简介 近年来,深度卷积神经网络在计算机视觉上取得了优异的性能。深度卷积神经网络以精确地分类目标信息而闻名,并采用了简单的卷积体系结构来降低图层的复杂性。基于深度卷积神经网络概念设计的VGG网络。VGGNet在对大规模图像进行分类方面取得了巨大…...

【STM32单片机】数学自动出题器设计
文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器,使用按键、IIC OLED模块等。 主要功能: 系统运行后,OLED液晶显示出题器开机界面,默认结果范围为100,可按…...

C语言之动态内存管理篇(1)
目录 为什么存在动态内存分配 动态内存函数的介绍 malloc free calloc realloc 常见的动态内存错误 今天收假了,抓紧时间写几篇博客。我又来赶进度了。今天我们来讲解动态内存管理。🆗🆗 为什么存在动态内存分配 假设我们去实现一个…...

React18入门(第二篇)——React18+Ts项目配置husky、eslint、pretttier、commitLint
前言 我的项目版本如下: React: V18.2.0Node.js: V16.14.0TypeScript:最新版工具: VsCode 本文将采用图文详解的方式,手把手带你快速完成在React项目中配置husky、prettier、commitLint,实现编码规范的统…...

【VINS】苹果手机采集单目相机+IMU数据离线运行VINS-Mono
0.准备工作 开个新坑,之前用Android手机做过离线采集数据的实验,这次用IPhone来测试! 1.虚拟机配置Mac OS 下载一个Mac OS 的ios镜像,打开虚拟机按照跟Ubuntu差不多的方式安装,但是发现没有Mac OS的入口。 因为VMwa…...

数据结构 2.1 单链表
1.单链表 线性表:1.有限的序列 2.序列中的每一个元素都有唯一的前驱和后继,除了开头和结尾的两个节点。 顺序表:分配一块连续的内存去存放这些元素,eg、数组 链表:内存是不连续的,元素会各自被分配一块内…...

[Machine Learning]pytorch手搓一个神经网络模型
因为之前虽然写过一点点关于pytorch的东西,但是用的还是他太少了。 这次从头开始,尝试着搓出一个神经网络模型 (因为没有什么训练数据,所以最后的训练部分使用可能不太好跑起来的代码作为演示,如果有需要自己连上数据…...

KdMapper扩展实现之Dell(pcdsrvc_x64.pkms)
1.背景 KdMapper是一个利用intel的驱动漏洞可以无痕的加载未经签名的驱动,本文是利用其它漏洞(参考《【转载】利用签名驱动漏洞加载未签名驱动》)做相应的修改以实现类似功能。需要大家对KdMapper的代码有一定了解。 2.驱动信息 驱动名称pcds…...

python和go相互调用的两种方法
前言 Python 和 Go 语言是两种不同的编程语言,它们分别有自己的优势和适用场景。在一些项目中,由于团队内已有的技术栈或者某一部分业务的需求,可能需要 Python 和 Go 相互调用,以此来提升效率和性能。 性能优势 Go 通常比 Python 更高效&…...
c# 分部视图笔记
Html.Partial("**", 1) public ActionResult **(int page) { ViewBag.page page; return PartialView("**"); }...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...

Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看
文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...