【算法】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)就算是大文件,…...
KDS安装步骤
KDS kinetis design studio 软件 第一步官网(https://www.nxp.com/ 注册账号下载set成功下载软件。 随着AI,大数据这些技术的快速发展,与此有关的知识也普及开来。如何在众多网站中寻找最有价值的信息,如何在最短的时间内获得最新的技…...
JavaSE-线程池(1)- 线程池概念
JavaSE-线程池(1)- 线程池概念 前提 使用多线程可以并发处理任务,提高程序执行效率。但同时创建和销毁线程会消耗操作系统资源,虽然java 使用线程的方式有多种,但是在实际使用过程中并不建议使用 new Thread 的方式手…...
开源代码的寿命为何只有1年?
说实话,如果古希腊的西西弗斯是一个在2016年编写开源代码的开发者,那他会有宾至如归的感觉。著名的西西弗斯处罚,是神话流传下来的,他被迫推一块巨大的石头上山,当登顶之后,只能眼睁睁看着它滚下去…...
完善登录功能--过滤器的使用
系列文章目录 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;…...
驱动开发(二)
一、驱动流程 驱动需要以下几个步骤才能完成对硬件的访问和操作: 模块加载函数 module_init注册主次设备号 <应用程序通过设备号找到设备>驱动设备文件 <应用程序访问驱动的方式> 1、手动创建 (mknod)2、程序自动创建file_oper…...
《狂飙》大结局,这22句经典台词值得细品
最近爆火的热播剧《狂飙》大家都看了吗? 剧情紧凑、演技炸裂、豆瓣评分9.0,可以说是开年评分最高的一部国产剧。 虽然大结局了。 里面有很多经典台词,值得每个人细细品味。 01 这世界不缺梦想 有本事你就去实现它 02 你这么善良 怎么跟坏…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
