当前位置: 首页 > 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 你这么善良 怎么跟坏…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

快刀集(1): 一刀斩断视频片头广告

一刀流&#xff1a;用一个简单脚本&#xff0c;秒杀视频片头广告&#xff0c;还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农&#xff0c;平时写代码之余看看电影、补补片&#xff0c;是再正常不过的事。 电影嘛&#xff0c;要沉浸&#xff0c;…...