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

算法导论【字符串匹配】—朴素算法、Rabin-Karp、有限自动机、KMP

算法导论【字符串匹配】—朴素算法、Rabin Karp、有限自动机、KMP

  • 朴素字符串匹配算法
  • Rabin-Karp算法
  • 有限自动机
  • KMP算法

文本

在这里插入图片描述

朴素字符串匹配算法

  • 预处理时间0
  • 匹配时间O((n-m+1)m)
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

Rabin-Karp算法

  • 预处理时间Θ(m),需要预先算出匹配串的哈希值
  • 匹配时间O((n−m+1)m),匹配过程与朴素算法类似,但是不需要逐个比对,先比对哈希值,这样可以减少字符匹配次数,计算待匹配的m个字符的哈希值,采用特定方法可以只要常数时间
  • Rabin-Karp算法的预处理时间为Θ(m)\Theta(m)Θ(m),在最坏情况下,运行时间为Θ((n−m+1)m)\Theta((n-m+1)m)Θ((nm+1)m)
  • Rabin-Karp算法比较字符串的哈希值,而不是字符串本身。为了提高效率,可以从当前位置的哈希值轻松计算文本中下一个位置的哈希
  • 简单说就是:每次计算m个字符的字符串的哈希值,然后与匹配串的哈希值对比,如果不相等那这两个字符串肯定不一样,如果哈希值相等,那么再逐个匹配字符,这样可以减少不必要的匹配
  • 如果哈希值不相等,算法将计算下一个M字符序列的哈希值。如果哈希值相等,算法将比较模式和M字符序列。这样,每个文本子序列只有一个比较,只有当哈希值匹配时才需要字符匹配
  • Rabin Karp算法的预处理阶段包括计算哈希Hash(P)Hash(P)Hash(P)。它可以在恒定的空间和O(m)O(m)O(m)时间内完成。
  • 在搜索阶段,将哈希Hash(P)Hash(P)Hash(P)与哈希Hash(T[j..j+m−1])Hash(T[j..j+m−1])Hash(T[j..j+m1])比较就足够了。如果找到了一个等式,仍然需要逐个字符检查等式P=T[j..j+m−1]P=T[j..j+m−1]P=T[j..j+m1]
  • Rabin Karp算法的时间复杂度为Θ((n−m+1)m)=Θ(mn)Θ((n−m+1)m)=Θ(mn)Θ((nm+1)m)=Θ(mn)(例如,当在n中搜索m时)。当有效点很小时,例如O(1)O(1)O(1),其预期的文本字符比较数为O(n+m)=O(n)O(n+m)=O(n)O(n+m)=O(n)
  • 在这里插入图片描述
  • 在这里插入图片描述
  • 在这里插入图片描述
  • 在这里插入图片描述在这里插入图片描述
  • 在这里插入图片描述

有限自动机

  • 预处理时间O(|mΣ|),|Σ|为待匹配串的字母表大小
  • 匹配时间Θ(n),预处理完后只需要扫描一遍字符串即可找到匹配串
    在这里插入图片描述
    在这里插入图片描述

KMP算法

  • 预处理时间Θ(m)

  • 匹配时间Θ(n)

  • 关键在于计算出前缀π\piπ数组,π\piπ就是文本串中在该位置能够得到最长的前后缀长度,举个例子:在这里插入图片描述
    在这里插入图片描述

  • 预处理过程:在这里插入图片描述- 匹配过程:在这里插入图片描述

相关文章:

算法导论【字符串匹配】—朴素算法、Rabin-Karp、有限自动机、KMP

算法导论【字符串匹配】—朴素算法、Rabin Karp、有限自动机、KMP朴素字符串匹配算法Rabin-Karp算法有限自动机KMP算法朴素字符串匹配算法 预处理时间:0匹配时间:O((n-m1)m) Rabin-Karp算法 预处理时间:Θ(m),需要预先算出匹…...

如何在 Python 中验证用户输入

要验证用户输入: 使用 while 循环进行迭代,直到提供的输入值有效。检查输入值在每次迭代中是否有效。如果该值有效,则跳出 while 循环。 # ✅ 验证用户输入的是否是整数num 0while True:try:num int(input("Enter an integer 1-10: …...

JVM详解——类的加载

文章目录类的加载1、Java程序如何运行2、Java字节码文件3、类加载4、类加载的过程5、类加载器6、类的加载方式7、类的加载机制8、双亲委派机制9、破坏双亲委派机制类的加载 1、Java程序如何运行 首先通过Javac命令将.java文件编译生成.class字节码文件。 Javac是Java编译命令&a…...

Ubuntu最新版本(Ubuntu22.04LTS)安装nfs服务器及使用教程

目录 一、概述 二、在Ubuntu搭建nfs服务器  👉2.1 安装nfs服务器  👉2.2 创建nfs服务器共享目录  👉2.3 修改nfs服务器配置文件  👉2.4 重启nfs服务器 三、客户端访问nfs服务器共享目录  🎈3.1 在nfs客户端挂载服…...

Python-第九天 Python异常、模块与包

Python-第九天 Python异常、模块与包一、了解异常1. 什么是异常:2. bug是什么意思:二、异常的捕获方法1. 为什么要捕获异常?2. 捕获异常的语法3. 如何捕获所有异常?三、异常的传递性1.异常是具有传递性的四、Python模块1. 什么是模…...

博彩公司 BetMGM 发生数据泄露,“赌徒”面临网络风险

Bleeping Computer 网站披露,著名体育博彩公司 BetMGM 发生一起数据泄露事件,一名威胁攻击者成功窃取其大量用户个人信息。 据悉,BetMGM 数据泄漏事件中,攻击者盗取了包括用户姓名、联系信息(如邮政地址、电子邮件地址…...

初探Mysql反向读取文件

前言 Mysql反向读取文件感觉蛮有意思的,进行了解过后,简单总结如下,希望能对在学习Mysql反向读取文件的师傅有些许帮助。 前置知识 在Mysql中存在这样一条语句 LOAD DATA INFILE它的作用是读取某个文件中的内容并放置到要求的表中&#x…...

地图坐标系大全:常用地图坐标系详解与转换指南

介绍地图坐标系的基本概念和原理地图坐标系是用于描述地图上位置的数学模型。它可以用来表示地球表面上的任意一个点,使得这个点的位置可以在地图上精确定位。不同的地图坐标系采用不同的基准面和投影方式,因此会有不同的坐标系参数,不同的坐…...

使用 URLSearchParams 解析和管理URL query参数

介绍 首先 URLSearchParams是一个构造函数,会生成一个URLSearchParams对象,参数类型: 不传 | string | object | URLSearchParams, 并且遇到特殊字符它会自动帮我们encode 和 decode const ur…...

一台电脑安装26个操作系统(windows,macos,linux,chromeOS,Android,静待HarmonyOS)

首先看看安装了哪些操作系统1-4: windows系统 四个5.Ubuntu6.deepin7.UOS家庭版8.fydeOS9.macOS10.银河麒麟11.红旗OS12.openSUSE Leap13.openAnolis14.openEuler(未安装桌面UI)15.中标麒麟(NeoKylin)16.centos17.debian Edu18.fedora19.oraclelinux(特别…...

Python配置文件管理之ini和yaml文件读取

1. 引言 当我们设计软件时,我们通常会花费大量精力来编写高质量的代码。但这往往还不够,一个好的软件还应该考虑其整个系统,如测试、部署、网络等。其中最重要的一个方面是配置管理。 良好的配置管理应允许在任何环境中执行软件而不更改代码…...

实战一(下):如何利用基于充血模型的DDD开发一个虚拟钱包系统?

上一节课,我们做了一些理论知识的铺垫性讲解,讲到了两种开发模式,基于贫血模型的传统开发模式,以及基于充血模型的DDD开发模式。今天,我们正式进入实战环节,看如何分别用这两种开发模式,设计实现一个钱包系统。话不多说,让我们正式…...

webpack当中的代码分割详解

A.代码分割方法一:将原来的单入口文件改为多入口文件 将不同的文件例如js代码文件分为入口文件和测试文件,这个时候打包出来的代码就会根据不同的文件单独打包成属于他们自己的文件 例如以下为单入口文件: entry: ./src/js/index.js 多入口文件:(在输出…...

【SSM】Spring对IoC的实现方式DI详讲

控制反转的一种实现方式——依赖注入一、IoC 控制反转(Overview)依赖注入(DI)- Overview利用 IoC(控制反转)这种思想有什么好处呢?二、依赖注入的方式setter 方式(xml配置中的proper…...

【QT 5 相关实验-示波器-学习笔记-示波器组件练习与使用总结】

【QT 5 相关实验-示波器-学习笔记-示波器组件练习与使用总结】1、概述2、实验环境3、参考资料-致谢4、自我提升实验效果视频演示5、代码练习-学习后拆解-实验步骤(1)头文件部分-"mwaveview.h"(2)cpp文件部分-"mwav…...

二维数组中的查找(两种解法,各有千秋)

凡事都有可能,永远别说永远。——《放牛班的春天》今天一题为再一个行列都有序的二维数组中寻找一个目标值,我们第一时间想到的可能是很暴力的解法,例如从头到尾进行遍历,这样能做出来,但是借用武忠祥老师的一句话&…...

quartz使用及原理解析

quartz简介 ​ Quartz是OpenSymphony开源组织在Job scheduling领域又一个开源项目,完全由Java开发,可以用来执行定时任务,类似于java.util.Timer。但是相较于Timer, Quartz增加了很多功能: 持久性作业 - 就是保持调度…...

Datawhale组队学习:大数据 D2——分布式文件系统(HDFS)

妙趣横生大数据 Day2三、Hadoop 分布式文件系统(HDFS)1. 分布式文件系统2. HDFS 简介3. HDFS 体系结构4. HDFS存储原理数据冗余存储数据存储策略数据错误与恢复5. HDFS数据读写过程读写过程HDFS故障类型和其检测方法HDFS编程实验1. 本地和集群文件间操作2. 基本文件操作3. Hado…...

CCIE重认证-300-401-拖图题全

拖图 拖图题 编程 snippet;192.168.5.0,mask 255.255.255.0;number是192.168.5.0;mask是255.255.255.0 snippets;edit-config对config,loopback对name 100,address对primary,mask…...

如何动态的创建类?type的其他用法?什么是元类,如何自定义元类?

1、python中一切都是对象,类也不例外,type是object的子类,是创建类的类。 如何动态的创建一个类? 用脚丫子创建 用脑子创建 不会 不知道什么事动态类 大家可能会有一堆的疑惑,是的我也是有很多疑惑那让我们一起来探个…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

linux arm系统烧录

1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 &#xff08;忘了有没有这步了 估计有&#xff09; 刷机程序 和 镜像 就不提供了。要刷的时…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...