关键词查找【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 算法】 【算法】哪种算法有分数复杂度?- BoyerMoore字符串匹配_哔哩哔哩_bilibili BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较,而…...
【前端手写代码】手写Object.create
思路:将传入的对象作为原型 // 思路:将传入的对象作为原型 function create(obj) {function F() { }F.prototype objreturn new F() }...

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

HamonyOS性能优化工具和方法
性能优化,如何做到更快的启动、更流畅的使用,概括图如下 ArkTS高性能编程: 1. ArkTS规则:有利于方舟编译运行时进行编译优化 2. 使用AOT(Ahead Of Time)模式对应用进行编译优化:方舟编译运行时通过采用PGO(Profile-Gui…...
前端实现边下载文件边上传
问题记录原因: 因为需要实现网络文件的上传,结果是由前端实现,方式是一边下载,一遍上传文件,小文件直接上传,大文件进行切片,切片大小和下载大小有关,特此记录。 1.实现方案 fetc…...

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

K8s大模型算力调度策略的深度解析
随着大数据和人工智能技术的飞速发展,Kubernetes(简称K8s)作为容器编排的领军者,在支撑大规模模型训练和推理方面扮演着越来越重要的角色。在大模型算力的调度过程中,如何高效、合理地分配和管理资源成为了一个亟待解决…...
Unity Transform组件实现动画:基础与进阶技巧
在Unity中,Transform组件是控制游戏对象(GameObject)位置、旋转和缩放的核心组件。通过编程控制Transform组件,开发者可以创建各种动画效果。本文将介绍如何使用Transform组件实现动画,从基础的运动到更高级的动画技巧…...
基于深度学习的图像与文本结合
基于深度学习的图像与文本结合的研究领域,是近年来多模态学习(Multimodal Learning)中非常活跃的方向。该领域涉及到如何将图像和文本两种不同类型的数据进行融合和处理,从而实现更智能的任务和应用。以下是对这一领域的详细介绍&…...
windows安全加固
一、补丁管理 及时安装补丁:定期检查和安装Windows系统及其应用程序的更新和补丁,以修复已知的安全漏洞。可以使用Windows Update功能或第三方补丁管理工具来实现。补丁管理策略:对于无法直接访问互联网的服务器,可以建立内部补丁…...

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

语义分割介绍
1. 定义 语义指具有人们可用语言探讨的意义,分割指图像分割。 语义分割(semantic segmentation)能够将整张图的每个部分分割开,使每个部分都有一定类别意义(语义),让计算机可以理解图像。 语义分割是以描边的形式&…...
Unity Editor免登录启动 无需UnityHub
Unity Editor免登录启动项目无需UnityHub,命令行启动项目。需要开发Unity项目,就必须使用 Unity Hub来管理你的项目,还必须要申请一个免费许可,确实有点麻烦,官方已经提供了相关命令行,来直接使用Unity Edi…...

Redis实战篇(黑马点评)笔记总结
一、配置前后端项目的初始环境 前端: 对前端项目在cmd中进行start nginx.exe,端口号为8080 后端: 配置mysql数据库的url 和 redis 的url 和 导入数据库数据 二、登录校验 基于Session的实现登录(不推荐) …...

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

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

mac OS matplotlib missing from font(s) DejaVu Sans
如果能搜索到这篇文章,我猜你遇到了和我一样的问题:matplotlib绘图中文乱码。如下: 出现这个问题的原因是:matplotlib使用的字体列表中默认没有中文字体。 这里说一种解决方案:我们可以在文件中手动指定matplotlib使用…...
在 .NET 中使用 Elasticsearch:从安装到实现搜索功能的完整指南
在 .NET 中使用 Elasticsearch Elasticsearch 是一个强大的搜索和分析引擎,广泛应用于处理大规模数据和实时搜索需求。本文将介绍如何在 .NET 环境下使用 Elasticsearch,帮助开发者快速上手并实现基本的搜索功能。 1. 环境准备 首先,我们需…...

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

git sendemail使用
教程参考: 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…...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Cesium1.95中高性能加载1500个点
一、基本方式: 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...