当前位置: 首页 > news >正文

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算法&#xff0c;即暴力(Brute Force)算法&#xff0c;是普通的模式匹配算法&#xff0c;BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配&#xff0c;若相等&#xff0c;则继…...

零基础转行网络工程师,过来人给的一些建议

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

Vue中如何进行分布式搜索与全文搜索(如Elasticsearch)

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

数据结构-图-最小生成树问题

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

使用vite+npm封装组件库并发布到npm仓库

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

85.最大矩形

单调栈&#xff0c;时间复杂度o(mn)&#xff0c;空间复杂度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&#xff0c;并粘贴下面脚本 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"说明&#xff0c;脚本格式为&#xff1a;start cmd /k “cd /d…...

《算法通关之路》chapter17一些通用解题模板

《算法通关之路》学习笔记&#xff0c;记录一下自己的刷题过程&#xff0c;详细的内容请大家购买作者的书籍查阅。 1 二分法 1.1 普通二分法 # 查找nums数组中元素值为target的下标。如果不存在&#xff0c;则返回-1def bs(nums: list[int], target: int) -> int :l, h …...

常用求解器安装

1 建模语言pyomo Pyomo是一个Python建模语言&#xff0c;用于数学优化建模。它可以与不同的求解器&#xff08;如Gurobi&#xff0c;CPLEX&#xff0c;GLPK&#xff0c;SCIP等&#xff09;集成使用&#xff0c;以求解各种数学优化问题。可以使用Pyomo建立数学优化模型&#xf…...

第三章:最新版零基础学习 PYTHON 教程(第一节 - Python 运算符)

在Python编程中,运算符一般用于对值和变量进行操作。这些是用于逻辑和算术运算的标准符号。在本文中,我们将研究不同类型的Python 运算符。 运算符:这些是特殊符号。例如- + 、 * 、 / 等。操作数:它是应用运算符的值。目录 Python 中的运算符类型 Python 中的算术运算符…...

细粒度特征提取和定位用于目标检测:PPCNN

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

【STM32单片机】数学自动出题器设计

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

C语言之动态内存管理篇(1)

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

React18入门(第二篇)——React18+Ts项目配置husky、eslint、pretttier、commitLint

前言 我的项目版本如下&#xff1a; React&#xff1a; V18.2.0Node.js: V16.14.0TypeScript&#xff1a;最新版工具&#xff1a; VsCode 本文将采用图文详解的方式&#xff0c;手把手带你快速完成在React项目中配置husky、prettier、commitLint&#xff0c;实现编码规范的统…...

【VINS】苹果手机采集单目相机+IMU数据离线运行VINS-Mono

0.准备工作 开个新坑&#xff0c;之前用Android手机做过离线采集数据的实验&#xff0c;这次用IPhone来测试&#xff01; 1.虚拟机配置Mac OS 下载一个Mac OS 的ios镜像&#xff0c;打开虚拟机按照跟Ubuntu差不多的方式安装&#xff0c;但是发现没有Mac OS的入口。 因为VMwa…...

数据结构 2.1 单链表

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

[Machine Learning]pytorch手搓一个神经网络模型

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

KdMapper扩展实现之Dell(pcdsrvc_x64.pkms)

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

python和go相互调用的两种方法

前言 Python 和 Go 语言是两种不同的编程语言&#xff0c;它们分别有自己的优势和适用场景。在一些项目中&#xff0c;由于团队内已有的技术栈或者某一部分业务的需求&#xff0c;可能需要 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&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 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 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

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在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...