当前位置: 首页 > 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…...

springboot 百货中心供应链管理系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;百货中心供应链管理系统被用户普遍使用&#xff0c;为方…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

多模态大语言模型arxiv论文略读(108)

CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题&#xff1a;CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者&#xff1a;Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...