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

【算法】kmp

KMP算法

名称由来

是由发明这个算法的三个科学家的名称首字母组成

作用

用于字符串的匹配问题

举例说明

字符串 aabaabaaf
模式串 aabaaf

传统匹配方法

第一步

aabaabaaf
aabaaf

此时,b和f不一致,则把模式串从头和文本串的第二个字符开始比

第二步

aabaabaaf
_aabaaf

。。。。。以此类推,知道找到相同的或者结束

KMP算法

第一步

aabaabaaf
aabaaf

此时,b和f不一致,但是b和f前面的子串 aabaa
拥有最长相等前后缀2,因此可以跳过前两个字符 aa
,直接用文本串的 b 和 模式串的第三个字符继续比较

第二步

aabaabaaf
___aabaaf

。。。。。以此类推,知道找到相同的或者结束

最长相等前后缀

定义,以aabaa 为例
前缀:不包括最后一个字符
a
aa
aab
aaba

后缀:不包括第一个字符
a
aa
baa
abaa

最长相等前后缀就是 aa 长度为2

每一个字符串都对应一个最长相等前后缀表
aabaa
next[5] 0 1 0 1 2

如何求next表

初始化

next[0]=0

根据定义,单个字符,没有前后缀,最大公共长度自然为0

定义j=0,表示0…j为最长公共前后缀

定义i=1,从arr[1]开始遍历,求next[1]。。。

过程模拟

next[1]==next[0] 即next[i]==next[j]表示0…1(即0…i)子串aa的最大公共前后缀为0…0( 即0…j)a

j++

i++

next[2]!=next[1] 即next[i]!=next[j]表示0…1(即0…i)子串aa的最大公共前后缀为0…0( 即0…j)a

相关文章:

【算法】kmp

KMP算法 名称由来 是由发明这个算法的三个科学家的名称首字母组成 作用 用于字符串的匹配问题 举例说明 字符串 aabaabaaf 模式串 aabaaf 传统匹配方法 第一步 aabaabaaf aabaaf 此时,b和f不一致,则把模式串从头和文本串的第二个字符开始比 第…...

git 常用命令之 git checkout

大家好,我是 17。 git checkout 是 git 中最重要最常用的命令之一,本文为大家详细解说一下。 恢复工作区 checkout 的用途之一是恢复工作区。 git checkout . checkout . 表示恢复工作区的所有更改,未跟踪的文件不会有变化。 恢复工作区的所有文件风…...

一些常见错误

500状态码: 代表服务器业务代码出错, 也就是执行controller里面的某个方法的过程中报错, 此时在IDEA的控制台中会显示具体的错误信息, 所以需要去看IDEA控制台的报错404状态码: 找不到资源找不到静态资源 检查请求地址是否拼写错误 检查静态资源的位置是否正确 如果以上都没有问…...

[单片机框架][调试功能] 回溯案发现场

程序莫名死机跑飞,不知道问题,那么下面教你回溯错误源 回溯案发现场一、修改HardFault_Handler1. xx.s 在启动文件,找到HardFault_Handler。并修改。2. 定义HardFault_Handler_C函数。(主要是打印信息并存储Flash)3. 根…...

MySQL主从同步-(二)搭建从机服务器

在docker中创建并启动MySQL从服务器:**端口3307docker run -d \-p 3307:3306 \-v /atguigu/mysql/slave1/conf:/etc/mysql/conf.d \-v /atguigu/mysql/slave1/data:/var/lib/mysql \-e MYSQL_ROOT_PASSWORD123456 \--name atguigu-mysql-slave1 \mysql:8.0.3创建MyS…...

Linux系列 备份与分享文档

作者简介:一名在校云计算网络运维学生、每天分享网络运维的学习经验、和学习笔记。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页​​​​​​ 目录 前言 一.备份与分享文档 1.使用压缩和解压缩工具 (1&…...

SNI生效条件 - 补充nginx-host绕过实例复现中SNI绕过的先决条件

文章目录1.前置环境搭建2.测试SNI生效条件(时间)3. 证书对SNI的影响3.1 双方使用同一个证书:3.2 双方使用不同的证书与私钥4. 端口号区分测试4.1 端口号区分,证书区分:4.2 端口号区分,证书不区分:5.总结SNI运行机制6. SNI机制绕过…...

傻白探索Chiplet,Modular Routing Design for Chiplet-based Systems(十一)

阅读了Modular Routing Design for Chiplet-based Systems这篇论文,是关于多chiplet通信的,个人感觉核心贡献在于实现了 deadlock-freedom in multi-chiplet system,而不仅仅是考虑单个intra-chiplet的局部NoC可以通信,具体的一些…...

C语言静态库、动态库的封装和注意事项

1、动态库、静态库介绍 参考博客:《静态库和动态库介绍以及Makefile》; 2、代码目录结构和编译脚本 参考博客:《实际工作开发中C语言工程的目录结构分析》; 3、编写库的流程 (1)明确需求:需求是否合理、需求的使用场景、需求可能遇…...

MyBatis-Plus分页插件和MyBatisX插件

MyBatis-Plus分页插件和MyBatisX插件六、插件1、分页插件a>添加配置类b>测试八、代码生成器1、引入依赖2、快速生成十、MyBatisX插件1、新建spring boot工程a>引入依赖b>配置application.ymlc>连接MySQL数据库d>MybatisX逆向生成2、MyBatisX快速生成CRUD申明…...

年前无情被裁,面试大厂的这几个月…

2月份了,金三银四也即将来临,在这个招聘季,大厂也开始招人,但还是有很多人吐槽说投了很多简历,却迟迟没有回复… 另一面企业招人真的变得容易了吗?有企业HR吐槽,简历确实比以前多了好几倍&…...

基于Java的分片上传功能

起因:最近在工作中接到了一个大文件上传下载的需求,要求将文件上传到share盘中,下载的时候根据前端传的不同条件对单个或多个文件进行打包并设置目录下载。 一开始我想着就还是用老办法直接file.transferTo(newFile)就算是大文件&#xff0c…...

KDS安装步骤

KDS kinetis design studio 软件 第一步官网(https://www.nxp.com/ 注册账号下载set成功下载软件。 随着AI,大数据这些技术的快速发展,与此有关的知识也普及开来。如何在众多网站中寻找最有价值的信息,如何在最短的时间内获得最新的技…...

JavaSE-线程池(1)- 线程池概念

JavaSE-线程池(1)- 线程池概念 前提 使用多线程可以并发处理任务,提高程序执行效率。但同时创建和销毁线程会消耗操作系统资源,虽然java 使用线程的方式有多种,但是在实际使用过程中并不建议使用 new Thread 的方式手…...

开源代码的寿命为何只有1年?

说实话,如果古希腊的西西弗斯是一个在2016年编写开源代码的开发者,那他会有宾至如归的感觉。著名的西西弗斯处罚,是神话流传下来的,他被迫推一块巨大的石头上山,当登顶之后,只能眼睁睁看着它滚下去&#xf…...

完善登录功能--过滤器的使用

系列文章目录 Spring Boot读取配置文件内容的三种方式 Spring Boot自动配置–如何切换内置Web服务器 SpringBoot项目部署 上述为该系列部分文章,想了解更多可看我博客主页哦! 文章目录系列文章目录前言一、创建自定义过滤器LoginCheckFilter二、在启动类…...

CSS基础:属性和关系选择器

字体属性 color 文本颜色 div{ color:red;} div{ color:#ff0000;} div{ color:rgb(255,0,0);} div{ color:rgba(255,0,0,.5);}font-size 文本大小 h1 {font-size:40px;} h2 {font-size:30px;} p {font-size:14px;}注意:chrome浏览器接受最小字体是12px font-we…...

设计模式:原型模式解决对象创建成本大问题

一、问题场景 现在有一只猫tom,姓名为: tom, 年龄为:1,颜色为:白色,请编写程序创建和tom猫属性完全相同的10只猫。 二、传统解决方案 public class Cat {private String name;private int age;private String color;…...

驱动开发(二)

一、驱动流程 驱动需要以下几个步骤才能完成对硬件的访问和操作&#xff1a; 模块加载函数 module_init注册主次设备号 <应用程序通过设备号找到设备>驱动设备文件 <应用程序访问驱动的方式> 1、手动创建 &#xff08;mknod&#xff09;2、程序自动创建file_oper…...

《狂飙》大结局,这22句经典台词值得细品

最近爆火的热播剧《狂飙》大家都看了吗&#xff1f; 剧情紧凑、演技炸裂、豆瓣评分9.0&#xff0c;可以说是开年评分最高的一部国产剧。 ​ 虽然大结局了。 里面有很多经典台词&#xff0c;值得每个人细细品味。 01 这世界不缺梦想 有本事你就去实现它 02 你这么善良 怎么跟坏…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

JAVA后端开发——多租户

数据隔离是多租户系统中的核心概念&#xff0c;确保一个租户&#xff08;在这个系统中可能是一个公司或一个独立的客户&#xff09;的数据对其他租户是不可见的。在 RuoYi 框架&#xff08;您当前项目所使用的基础框架&#xff09;中&#xff0c;这通常是通过在数据表中增加一个…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...