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

字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)

朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),最为简单的字符串匹配算法。

算法简介

朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),它的主要特点是:
  • 没有预处理阶段;

  • 滑动窗口总是后移 1 位;

  • 对模式中的字符的比较顺序不限定,可以从前到后,也可以从后到前;

  • 匹配阶段需要 O((n - m + 1)m) 的时间复杂度;

  • 需要 2n 次的字符比较;

很显然,朴素的字符串匹配算法 NAIVE-STRING-MATCHER 是最原始的算法,它通过使用循环来检查是否在范围 n-m+1 中存在满足条件 P[1..m] = T [s + 1..s + m] 的有效位移 s。

伪代码如下:

NAIVE-STRING-MATCHER(T, P)n ← length[T]m ← length[P]for s ← 0 to n - mdoif P[1.. m]= T[s + 1.. s + m]then print "Pattern occurs with shift" s

如上图中,对于模式 P = aab 和文本 T = acaabc,将模式 P 沿着 T 从左到右滑动,逐个比较字符以判断模式 P 在文本 T 中是否存在。

可以看出,NAIVE-STRING-MATCHER 没有对模式 P 进行预处理,所以预处理的时间为 0。而匹配的时间在最坏情况下为 Θ((n-m+1)m),如果 m = [n/2],则为 Θ(n2)。

图例分析

假设有两个字符串:

  • M="abcdefabcdx";

  • T="abcdx";

想要找到T串在M串中的位置,要怎么找呢?

也就是说,从主串M的第一个字符开始分别与子串从开头进行比较,当发现不匹配时,主串回到这一轮开始的下一个字符,子串从头开始比较。直到子串所有的字符都匹配,返回所在主串中的下标。

算法复杂度

假设S的长度是m,T的长度是n,暂不考虑pos,从字符串S的开头开始比较。

  • 最好的情况是第一次就匹配了,需要比较的次数是n.

  • 最坏的情况下,就是上面举的这种例子,需要把整个字符串都比较完,从下面的代码中就体现为把两层循环都跑了一遍。这时候,比较的次数就是t*(s-t+1).

所以这个算法的(最坏)时间复杂度就是o(t(s-t+1)),近似为o(n2).

相关文章:

字符串匹配 - 模式预处理:朴素算法(Naive)(暴力破解)

朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),最为简单的字符串匹配算法。算法简介朴素的字符串匹配算法又称为暴力匹配算法(Brute Force Algorithm),它的主要特点是:没有预…...

CVE-2021-42278 CVE-2021-42287域内提权漏洞

漏洞介绍2021 年 11 月 9 日,国外研究员在推特上发布了AD相关的 CVE,CVE-2021-42278 & CVE-2021-42287 ,两个漏洞组合可导致域内普通用户权限提升至域管权限。CVE-2021-42278:是一个安全绕过漏洞,允许通过修改机器…...

关于IcmpSendEcho2的使用和回调问题

由于我的需求是短时间内ping多台机子,所以需要异步执行,微软提供的例子是同步方式的,根据微软官方提供的icmpSendEcho2 函数的信息 ,我需要定义一个空的宏PIO_APC_ROUTINE_DEFINED ,定义完之后,编译又出现…...

XQuery 术语

在 XQuery 中,有七种节点:元素、属性、文本、命名空间、处理指令、注释、以及文档节点(或称为根节点)。 XQuery 术语 节点 在 XQuery 中,有七种节点:元素、属性、文本、命名空间、处理指令、注释、以及文…...

会议论文分享-Security22-状态感知符号执行

Ferry: State-Aware Symbolic Execution for Exploring State-Dependent Program Paths1.引言2.问题陈述与分析2.1.实现状态感知符号执行的挑战2.2.真实程序的特征2.3.Ferry的模型2.3.1.程序状态的定义2.3.2.状态描述变量的特征3.Design3.1.Overview of Ferry3.2.状态描述变量识…...

吴恩达深度学习笔记(八)——卷积神经网络(上)

一、卷积相关 用一个ff的过滤器卷积一个nn的图像,假如padding为p,步幅为s,输出大小则为: [n2p−fs1][n2p−fs1][\frac{n2p-f}{s}1][\frac{n2p-f}{s}1][sn2p−f​1][sn2p−f​1] []表示向下取整(floor) 大部分深度学习…...

14 基数排序(桶排序)

文章目录1 基数排序基本思想2 基数排序的代码实现2.1 java2.2 scala3 基数排序总结1 基数排序基本思想 1) 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort&#…...

汉明距离Java解法

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。 给你两个整数 x 和 y,计算并返回它们之间的汉明距离。 例: 输入:x 1, y 4 输出:2 解释: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上…...

Netty服务端请求接受过程源码剖析

目标 服务器启动后,客户端进行连接,服务器端此时要接受客户端请求,并且返回给客户端想要的请求,下面我们的目标就是分析Netty 服务器端启动后是怎么接受到客户端请求的。我们的代码依然与上一篇中用同一个demo, 用io.…...

金三银四春招特供|高质量面试攻略

🔰 全文字数 : 1万5千 🕒 阅读时长 : 20min 📋 关键词 : 求职规划、面试准备、面试技巧、谈薪职级 👉 公众号 : 大摩羯先生 本篇来聊聊一个老生常谈的话题————“面试”。利用近三周工作午休时间整理了这篇洋洋洒洒却饱含真诚…...

搭建Hexo博客-第4章-绑定自定义域名

搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 搭建Hexo博客-第4章-绑定自定义域名 在这一篇文章中,我将会介绍如何给博客绑定你自己的域名。其实绑定域名本应该很简单的,但我当初在这上走了不少弯路,所以我觉得有…...

lightdb-sql拦截

文章目录LightDB - sql 审核拦截一 简介二 参数2.1 lightdb_sql_mode2.2 lt_firewall.lightdb_business_time三 规则介绍及使用3.1 select_without_where3.1.1 案例3.2 update_without_where/delete_without_where3.2.1 案例3.3 high_risk_ddl3.3.1 案例LightDB - sql 审核拦截…...

二进制中1的个数-剑指Offer-java位运算

一、题目描述编写一个函数,输入是一个无符号整数(以二进制串的形式),返回其二进制表达式中数字位数为 1 的个数(也被称为 汉明重量).)。提示:请注意,在某些语言(如 Java&…...

学自动化测试可以用这几个练手项目

练手项目的业务逻辑比较简单,只适合练手,不能代替真实项目。 学习自动化测试最难的是没有合适的项目练习。 测试本身既要讲究科学,又有艺术成分,单单学几个 api 的调用很难应付工作中具体的问题。 你得知道什么场景下需要添加显…...

2023年保健饮品行业分析:市场规模不断攀升,年度销额增长近140%

随着人们健康意识的不断增强,我国保健品市场需求持续增长,同时,保健饮品的市场规模也在不断攀升。 根据鲸参谋电商数据显示,2022年度,京东平台上保健饮品的年度销量超60万件,同比增长了约124%;该…...

2023-02-17 学习记录--TS-邂逅TS(一)

TS-邂逅TS(一) 不积跬步,无以至千里;不积小流,无以成江海。💪🏻 一、TypeScript在线编译器 https://www.typescriptlang.org/play/ 二、类型 1、普通类型 number(数值型&#xff…...

SpringMVC创建异步回调请求的4种方式

首先要明确一点,同步请求和异步请求对于客户端用户来讲是一样的,都是需客户端等待返回结果。不同之处在于请求到达服务器之后的处理方式,下面用两张图解释一下同步请求和异步请求在服务端处理方式的不同:同步请求异步请求两个流程…...

MySQL(二)表的操作

一、创建表 CREATE TABLE table_name ( field1 datatype, field2 datatype, field3 datatype ) character set 字符集 collate 校验规则 engine 存储引擎; 说明: field 表示列名 datatype 表示列的类型 character set 字符集,如…...

SpringCloud - 入门

目录 服务架构演变 单体架构 分布式架构 分布式架构要考虑的问题 微服务 初步认识 案例Demo 服务拆分注意事项 服务拆分示例 服务调用 服务架构演变 单体架构 将业务的所有功能集中在一个项目中开发,打成一个包部署优点: 架构简单部署成本低缺…...

进一步了解C++函数的各种参数以及重载,了解C++部分的内存模型,C++独特的引用方式,巧妙替换指针,初步了解类与对象。满满的知识,希望大家能多多支持

C的编程精华,走过路过千万不要错过啊!废话少说,我们直接进入正题!!!! 函数高级 C的函数提高 函数默认参数 在C中,函数的形参列表中的形参是可以有默认值的。 语法:返…...

Chapter6:机器人SLAM与自主导航

ROS1{\rm ROS1}ROS1的基础及应用,基于古月的课,各位可以去看,基于hawkbot{\rm hawkbot}hawkbot机器人进行实际操作。 ROS{\rm ROS}ROS版本:ROS1{\rm ROS1}ROS1的Melodic{\rm Melodic}Melodic;实际机器人:Ha…...

Sass的使用要点

Sass 是一个 CSS 预处理器,完全兼容所有版本的 CSS。实际上,Sass 并没有真正为 CSS 语言添加任何新功能。只是在许多情况下可以可以帮助我们减少 CSS 重复的代码,节省开发时间。 一、注释 方式一:双斜线 // 方式二:…...

计算机启动过程,从按下电源按钮到登录界面的详细步骤

1、背景 自接触计算机以来,一直困扰着我一个问题。当我们按下电脑的开机键后,具体发生了哪些过程呢?计算机启动的具体步骤是什么? 计算机启动过程通常分为五个步骤:电源自检、BIOS自检、引导设备选择、引导程序加载和…...

LeetCode 刷题之 BFS 广度优先搜索【Python实现】

1. BFS 算法框架 BFS:用来搜索 最短路径 比较合适,如:求二叉树最小深度、最少步数、最少交换次数,一般与 队列 搭配使用,空间复杂度比 DFS 大很多DFS:适合搜索全部的解,如:寻找最短…...

Hadoop01【尚硅谷】

大数据学习笔记 大数据概念 大数据:指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。 主要解决,海量数据的存储…...

Echarts 配置横轴竖轴指示线,更换颜色、线型和大小

第018个点击查看专栏目录本示例是描述如何在Echarts上配置横轴竖轴指示线,更换颜色、线型和大小。方法很简单,参考示例源代码。 文章目录示例效果示例源代码(共85行)相关资料参考专栏介绍示例效果 示例源代码(共85行&a…...

OpenAI 官方API Java版SDK,两行代码即可调用。包含GhatGPT问答接口。

声明:这是一个非官方的社区维护的库。 已经支持OpenAI官方的全部api,有bug欢迎朋友们指出,互相学习。 注意:由于这个接口: https://platform.openai.com/docs/api-reference/files/retrieve-content 免费用户无法使…...

SpringBoot 日志文件

(一)日志文件有什么用?除了发现和定位问题之外,我们还可以通过日志实现以下功能:记录用户登录日志,以便分析用户是正常登录还是恶意破解用户。记录系统的操作日志,以便数据恢复和定位操作 。记录程序的执行时间&#x…...

SQL71 检索供应商名称

描述Vendors表有字段供应商名称(vend_name)、供应商国家(vend_country)、供应商州(vend_state)vend_namevend_countryvend_stateappleUSACAvivoCNAshenzhenhuaweiCNAxian【问题】编写 SQL 语句,…...

02:入门篇 - 漫谈 CTK

作者: 一去、二三里 个人微信号: iwaleon 微信公众号: 高效程序员 十万个为什么 五千个在哪里?七千个怎么办?十万个为什么?。。。生活中,有很多奥秘在等着我们去思考、揭示! 同样地,在使用 CTK 时,很多小伙伴一定也存在诸多疑问: 为什么 CTK Plugin Framework 要借…...

wordpress vieu/天津百度爱采购

前面在PROFILE中增加了用户最近采购记录的显示,其中包括显示用户的最近的累计采购金额,我这边是根据用户的采购金额来显示用户采购的金额区间,但是这其中我没有问这个金额DW那边返回的是什么的样的单位,甚至于上周五晚上的时候有客…...

怎么做中英文双语网站/网络的推广

如果想了解更多的知识,可以去我的机器学习之路 The Road To Machine Learning通道 第3章 k近邻法 1.kkk近邻法是基本且简单的分类与回归方法。kkk近邻法的基本做法是:对给定的训练实例点和输入实例点,首先确定输入实例点的kkk个…...

wordpress图文主题/怎么把产品快速宣传并推广

一、vertical aglin之数值百分比 数值类和百分比类 1.共性: a.都带数字 b.都支持负值(支持负值的css有:margin、letter-spacing、word-spacing、vertical-align) c.行为表现一致 百分比:vertical aglin的百分比是相对于line-height计算的! IE6/IE7下 vertical aglin的百分比不支…...

广州天河区做网站的公司/关键词排名优化价格

2019独角兽企业重金招聘Python工程师标准>>> 1、MySQL的复制原理以及流程 基本原理流程,3个线程以及之间的关联; 主:binlog线程——记录下所有改变了数据库数据的语句,放进master上的binlog中;从&#xff1…...

万网网站 banner图片不显示/seo分析报告怎么写

HDM(H3C Device Management,H3C设备管理)系统是H3C UIS服务器的一个标准组件,通过它可以简化服务器初始设置、监控服务器运行状况、优化电源和散热系统以及对服务器进行远程管理等。HDM系统依靠智能微处理器、专用内存和共享网络接口等技术,实…...

代码需求网站/深圳关键词推广

php程序员工具箱是一款php程序员的专属工具箱,简称:php工具箱,设计人员将程序员开发需要用到的工具都汇集到该工具箱中,它我可以为开发人员提供非常多的便捷;用户可以直接通过该程序进行程序开发,可以通过它…...