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

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

Springboot社区养老保险系统小程序

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

echarts使用graphic强行给图增加一个边框(边框根据自己的图形大小设置)- 适用于无法使用dom的样式

pdf-lib https://blog.csdn.net/Shi_haoliu/article/details/148157624?spm1001.2014.3001.5501 为了完成在pdf中导出echarts图&#xff0c;如果边框加在dom上面&#xff0c;pdf-lib导出svg的时候并不会导出边框&#xff0c;所以只能在echarts图上面加边框 grid的边框是在图里…...

云原生时代的系统设计:架构转型的战略支点

&#x1f4dd;个人主页&#x1f339;&#xff1a;一ge科研小菜鸡-CSDN博客 &#x1f339;&#x1f339;期待您的关注 &#x1f339;&#x1f339; 一、云原生的崛起&#xff1a;技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深&#xff0c;传统的 I…...