当前位置: 首页 > 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("**"); }...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

mac 安装homebrew (nvm 及git)

mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用&#xff1a; 方法一&#xff1a;使用 Homebrew 安装 Git&#xff08;推荐&#xff09; 步骤如下&#xff1a;打开终端&#xff08;Terminal.app&#xff09; 1.安装 Homebrew…...

WebRTC从入门到实践 - 零基础教程

WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC&#xff1f; WebRTC&#xff08;Web Real-Time Communication&#xff09;是一个支持网页浏览器进行实时语音…...