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

关键词查找【Boyer-Moore 算法】

1、【Boyer-Moore 算法】

【算法】哪种算法有分数复杂度?- BoyerMoore字符串匹配_哔哩哔哩_bilibili

         BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较,而会跳过其中某些部分。通常搜索关键字越长,算法速度越快。它的效率来自于这样的事实:对于每一次失败的匹配尝试,算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征,加快了搜索的步骤。
           BM算法实际上包含两个并行的算法(也就是两个启发策略):坏字符算法(bad-character shift)和好后缀算法(good-suffix shift)。这两种算法的目的就是让模式串每次向右移动尽可能大的距离(即上面的BM( )尽可能大)。

          一般情况下,比KMP算法快3-5倍

package com.vedeng;public class BoyerMoore {private static final int NO_OF_CHARS = 256;// 预处理坏字符规则private static void badCharHeuristic(char[] str, int size, int[] badChar) {for (int i = 0; i < NO_OF_CHARS; i++) {badChar[i] = -1;}for (int i = 0; i < size; i++) {badChar[(int) str[i]] = i;}}// Boyer-Moore算法实现public static void search(char[] txt, char[] pat) {int m = pat.length;int n = txt.length;int[] badChar = new int[NO_OF_CHARS];// 预处理坏字符规则badCharHeuristic(pat, m, badChar);int s = 0; // s是shift的缩写,表示模式串相对于文本串的偏移while (s <= (n - m)) {int j = m - 1;// 从右向左匹配while (j >= 0 && pat[j] == txt[s + j]) {j--;}// 如果匹配成功,打印匹配的位置if (j < 0) {System.out.println("Patterns occur at shift = " + s);// 根据好后缀规则计算下一个可能的偏移s += (s + m < n) ? m - badChar[txt[s + m]] : 1;} else {// 根据坏字符规则计算下一个可能的偏移s += Math.max(1, j - badChar[txt[s + j]]);}}}public static void main(String[] args) {char[] txt = "ABAAABCD".toCharArray();char[] pat = "ABC".toCharArray();search(txt, pat);}
}

相关:

https://blog.csdn.net/qq_43197840/article/details/140680860?spm=1001.2014.3001.5501
https://blog.csdn.net/qq_43197840/article/details/140680621?spm=1001.2014.3001.5501

相关文章:

关键词查找【Boyer-Moore 算法】

1、【Boyer-Moore 算法】 【算法】哪种算法有分数复杂度&#xff1f;- BoyerMoore字符串匹配_哔哩哔哩_bilibili BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较&#xff0c;而…...

【前端手写代码】手写Object.create

思路&#xff1a;将传入的对象作为原型 // 思路&#xff1a;将传入的对象作为原型 function create(obj) {function F() { }F.prototype objreturn new F() }...

速通JS模块化规范

目录 1模块化概述 1.1什么是模块化&#xff1f; 1.2为什么需要模块化&#xff1f; 2有哪些模块化规范&#xff1f; 3导入与导出的概念 4CommonJS 规范 4.1初步体验 4.2导出数据 4.3导入数据 4.4扩展理解 4.5浏览器端运行 5ES6 模块化规范 5.1初步体验 5.2Node 中运…...

HamonyOS性能优化工具和方法

性能优化&#xff0c;如何做到更快的启动、更流畅的使用&#xff0c;概括图如下 ArkTS高性能编程&#xff1a; 1. ArkTS规则&#xff1a;有利于方舟编译运行时进行编译优化 2. 使用AOT(Ahead Of Time)模式对应用进行编译优化&#xff1a;方舟编译运行时通过采用PGO(Profile-Gui…...

前端实现边下载文件边上传

问题记录原因&#xff1a; 因为需要实现网络文件的上传&#xff0c;结果是由前端实现&#xff0c;方式是一边下载&#xff0c;一遍上传文件&#xff0c;小文件直接上传&#xff0c;大文件进行切片&#xff0c;切片大小和下载大小有关&#xff0c;特此记录。 1.实现方案 fetc…...

滑线变阻器的优缺点是什么?

滑线变阻器是常见的电子元件&#xff0c;主要用于调节电路中的电阻值&#xff0c;从而达到改变电流、电压的目的。它的主要优点是结构简单、操作方便、成本低&#xff0c;因此在各种电子设备中都有广泛的应用。然而&#xff0c;滑线变阻器也存在一些缺点&#xff0c;主要表现在…...

K8s大模型算力调度策略的深度解析

随着大数据和人工智能技术的飞速发展&#xff0c;Kubernetes&#xff08;简称K8s&#xff09;作为容器编排的领军者&#xff0c;在支撑大规模模型训练和推理方面扮演着越来越重要的角色。在大模型算力的调度过程中&#xff0c;如何高效、合理地分配和管理资源成为了一个亟待解决…...

Unity Transform组件实现动画:基础与进阶技巧

在Unity中&#xff0c;Transform组件是控制游戏对象&#xff08;GameObject&#xff09;位置、旋转和缩放的核心组件。通过编程控制Transform组件&#xff0c;开发者可以创建各种动画效果。本文将介绍如何使用Transform组件实现动画&#xff0c;从基础的运动到更高级的动画技巧…...

基于深度学习的图像与文本结合

基于深度学习的图像与文本结合的研究领域&#xff0c;是近年来多模态学习&#xff08;Multimodal Learning&#xff09;中非常活跃的方向。该领域涉及到如何将图像和文本两种不同类型的数据进行融合和处理&#xff0c;从而实现更智能的任务和应用。以下是对这一领域的详细介绍&…...

windows安全加固

一、补丁管理 及时安装补丁&#xff1a;定期检查和安装Windows系统及其应用程序的更新和补丁&#xff0c;以修复已知的安全漏洞。可以使用Windows Update功能或第三方补丁管理工具来实现。补丁管理策略&#xff1a;对于无法直接访问互联网的服务器&#xff0c;可以建立内部补丁…...

网络安全是什么?怎么入门网络安全?

一、网络安全的定义 网络安全&#xff0c;简单来说&#xff0c;就是保护网络系统中的硬件、软件以及其中的数据不因偶然或恶意的原因而遭到破坏、更改、泄露&#xff0c;保障系统连续可靠正常地运行&#xff0c;网络服务不中断。 随着信息技术的飞速发展&#xff0c;网络安全的…...

语义分割介绍

1. 定义 语义指具有人们可用语言探讨的意义&#xff0c;分割指图像分割。 语义分割(semantic segmentation)能够将整张图的每个部分分割开&#xff0c;使每个部分都有一定类别意义&#xff08;语义&#xff09;&#xff0c;让计算机可以理解图像。 语义分割是以描边的形式&…...

Unity Editor免登录启动 无需UnityHub

Unity Editor免登录启动项目无需UnityHub&#xff0c;命令行启动项目。需要开发Unity项目&#xff0c;就必须使用 Unity Hub来管理你的项目&#xff0c;还必须要申请一个免费许可&#xff0c;确实有点麻烦&#xff0c;官方已经提供了相关命令行&#xff0c;来直接使用Unity Edi…...

Redis实战篇(黑马点评)笔记总结

一、配置前后端项目的初始环境 前端&#xff1a; 对前端项目在cmd中进行start nginx.exe&#xff0c;端口号为8080 后端&#xff1a; 配置mysql数据库的url 和 redis 的url 和 导入数据库数据 二、登录校验 基于Session的实现登录&#xff08;不推荐&#xff09; &#xf…...

vulntarget-b

实际部署之后centos7 的ip有所变动分别是 :192.168.127.130以及10.0.20.30 Centos7 老规矩还是先用fscan扫一下服务和端口&#xff0c;找漏洞打 直接爆出来一个SSH弱口令…&#xff0c;上来就不用打了&#xff0c;什么意思&#xff1f;&#xff1f;&#xff1f; 直接xshell…...

Axure Web端元件库:构建高效互动网页的基石

在快速迭代的互联网时代&#xff0c;Web设计与开发不仅追求视觉上的美感&#xff0c;更注重用户体验的流畅与功能的强大。Axure RP&#xff0c;作为一款专业的原型设计工具&#xff0c;凭借其强大的交互设计能力和丰富的元件库&#xff0c;成为了众多UI/UX设计师、产品经理及前…...

mac OS matplotlib missing from font(s) DejaVu Sans

如果能搜索到这篇文章&#xff0c;我猜你遇到了和我一样的问题&#xff1a;matplotlib绘图中文乱码。如下&#xff1a; 出现这个问题的原因是&#xff1a;matplotlib使用的字体列表中默认没有中文字体。 这里说一种解决方案&#xff1a;我们可以在文件中手动指定matplotlib使用…...

在 .NET 中使用 Elasticsearch:从安装到实现搜索功能的完整指南

在 .NET 中使用 Elasticsearch Elasticsearch 是一个强大的搜索和分析引擎&#xff0c;广泛应用于处理大规模数据和实时搜索需求。本文将介绍如何在 .NET 环境下使用 Elasticsearch&#xff0c;帮助开发者快速上手并实现基本的搜索功能。 1. 环境准备 首先&#xff0c;我们需…...

Ecovadis认证的步骤需要怎么做?

Ecovadis是一家提供企业可持续发展评估和认证服务的机构。如果您想获得Ecovadis的认证辅导&#xff0c;可以按照以下步骤进行&#xff1a; 了解Ecovadis认证要求&#xff1a;在开始准备之前&#xff0c;先仔细研究Ecovadis的认证要求和标准。您可以访问Ecovadis的官方网站&…...

git sendemail使用

教程参考&#xff1a; git-send-email - 以电子邮件形式发送补丁集 1、安装git-email 2、配置 SMTP 服务器 git config --global sendemail.smtpserver smtp.163.com git config --global sendemail.smtpserverport 465 git config --global sendemail.smtpuser xxxxxx163.c…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...