KMP算法(JS)
KMP算法
什么时KMP算法
KMP算法是一种改进的字符串匹配算法
由D.E.Knuth,J.H.Morris和 V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。
KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。
所以如何记录已经匹配的文本内容,是KMP的重点,也就是next数组。
next数组
next数组其实就是模式字符串(模式串)的前缀表prefix
,前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。
要弄懂这些,我们首先要了解一下几点问题:
- 前缀:包含首位字符但不会包含末位字符的子串;
- 后缀:包含末位字符但不包含首位字符的子串。
- next数组的定义:当主串与模式串的某一字符不匹配时,模式串要回退的位置(即在匹配过程中,当一次匹配失败时,下一次的匹配不不用冲模式串的第一位位开始匹配);
- next[j]:其值 = 第j位字符前面j-1位字符组成的子串的前后重合字符数+1。
规律:
- next[j]的值每次最多增加1
- 模式串的组后一位字符不影响next数组的结果
求next[j]数组的代码:
/*** @param {string[]} ch* @param {int} length* @param {int[]} next*/
function getNext(needle) {let next = [];let j = 0;next.push(j);for (let i = 1; i < needle.length; ++i) {while (j > 0 && needle[i] !== needle[j])j = next[j - 1];if (needle[i] === needle[j])j++;next.push(j);}return next;
}
例:
j:1 2 3 4 5 6 p:a b a b a ?(模式串最后一位对next[j]数组是没有影响的)
next[j]:0 1 1 2 3 4
这里代码的主要思想是回溯,且next[i]值的意义是第i位字符前的字符串的最长公共前后缀的长度+1。
我们首先初始化next[1]=0
,接着在next[1]
基础上按顺序向后一一遍历,那么我们要求next[i]
的值时,我们即已经知道next[i-1]
的值假设它的值是j
,那么接意味着在数组中从第1
位第i-2
位的最长相等前后缀是j-1
,也就是说在模式串next[1] ~ next[i-2]
的范围中:1
~ j-1
和 i-j+1
~ i-2
这两段长度为j-1
的字符串是完全相等的。这是要分两种情况,即第j
位字符和第i-1
位字符相等,另一种是不相等:
- 这时一旦第
j
位字符和第i-1
位字符又相等的话,那么next[i]
的最长公共前后缀就是next[j-1]+1
,因为后缀多出来的一位字符和前缀多出来的一位字符相等,这是最长公共前后缀自然要加1。 - 但如果此时第
j
位字符和第i-1
位字符不相等,那么此时我们找第j位前的最长公共前后缀即next[j]-1
,此时我们可以知道next[0 ~ next[j-1]]
=next[next[j-1]-j+1 ~ j]
。也就是说,我们以j
为分隔点,先将模式串前后分为两段,前后两段除追后一位不相等外其他完全相等,那么前半部分满足这样的等式,意味着后半部分同样满足着这样的等式,即此时我们得到模式串的前i-1项又四段相等的子串,第一段和第四段相等。即next[0 ~ next[j-1]]
=next[next[j]-i+1 ~ i-2]
。到了这里是否似曾相识,没错,这里就是回溯第一遍的结果,那么再一次出现两种情况,即第next[j-1]+1项和i-1项时否相等:- 相等的话next[i]的最长公共前后缀,就是刚刚比较的两段子串的长度加1即
next[j-1]+1
。 - 若不相等,那么我们就需要再一次寻找相等的子串。此时将找到第
next[j-1]
位前的最长1公共前后缀。
- 相等的话next[i]的最长公共前后缀,就是刚刚比较的两段子串的长度加1即
- 依次循环,知道找到相等,或者即将回溯到下标为0时停止递归,此时说明没有公共前后缀,那么赋值为1也就是j+1(因为此时j为0)。
KMP模式匹配算法
var strStr = function (haystack, needle) {if (needle.length === 0)return 0;let next = getNext(needle);let j = 0;for (let i = 0; i < haystack.length; ++i) {while (j > 0 && haystack[i] !== needle[j])j = next[j - 1];if (haystack[i] === needle[j])j++;if (j === needle.length)return (i - needle.length + 1);}return -1;
};
相关文章:
KMP算法(JS)
KMP算法 什么时KMP算法 KMP算法是一种改进的字符串匹配算法 由D.E.Knuth,J.H.Morris和 V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。 KMP的主要思想是当出现字符串不匹配时,可以知道…...

恢复NuGet包_解决:System.BadImageFormatException:无法加载文件或程序集
C#工程 主要是开发了一个 web api接口,这个工程源码去年还可以的,今年换了一个电脑打开工程就报错。 错误提示如下: 在 Microsoft.CodeAnalysis.CSharp.CommandLine.Program.Main(String[] args) Test1 System.BadImageFormatEx…...

Django学习笔记(2)
创建app 属于自动执行了python manage.py 直接在里面运行startapp app01就可以创建app01的项目了 之后在setting.py中注册app01 INSTALLED_APPS ["django.contrib.admin","django.contrib.auth","django.contrib.contenttypes","django.c…...

高德地图开发者平台Python应用实践:快速入门周边商业环境信息查询
高德地图开发平台提供了丰富的API接口,可以方便地进行地图数据的开发和分析。在商业分析数据采集中,使用高德地图开发平台的周边查询功能可以快速获取周边商圈、小区等信息,为商业决策提供数据支持。 针对您的需求,我建议采用以下…...
【ES6】—let 声明方式
一、不属于顶层对象window let 关键字声明的变量,不会挂载到window的属性 var a 5 console.log(a) console.log(window.a) // 5 // 5 // 变量a 被挂载到window属性上了 , a window.alet b 6 console.log(b) console.log(window.b) // 6 // undefin…...

【数据分析入门】Jupyter Notebook
目录 一、保存/加载二、适用多种编程语言三、编写代码与文本3.1 编辑单元格3.2 插入单元格3.3 运行单元格3.4 查看单元格 四、Widgets五、帮助 Jupyter Notebook是基于网页的用于交互计算的应用程序。其可被应用于全过程计算:开发、文档编写、运行代码和展示结果。 …...
反射知识总结
1、反射概述 反射是指对于任何一个Class类,在"运行的时候"都可以直接得到这个类全部成分。在运行时,可以直接得到这个类的构造器对象:Constructor在运行时。可以直接得到这个类的成员变量对象:Field在运行时,…...

MongoDB 安装 linux
本文介绍一下MongoDB的安装教程。 系统环境:CentOS7.4 可以用 cat /etc/redhat-release 查看本机的系统版本号 一、MongoDB版本选择 当前最新的版本为7.0,但是由于7.0版本安装需要升级glibc2.25以上,所以这里我暂时不安装该版本。我们选择的是6.0.9版本…...

什么是KNN( K近邻算法)
什么是KNN( K近邻算法) 虽然名字中有NN,KNN并不是哪种神经网络,它全名K-Nearest-Neighbors:K近邻算法,是机器学习中常用的分类算法。 物以类聚,人以群分。KNN的基础思想很简单,要判断一个新数据的类别&…...
Linux查看命令总结
1.动态实时查找命令 使用以下命令的前提是需要在找到日志位置 tail -f server.log 实时展示日志末尾内容,默认最后10行,相当于增加参数 -n 10 tail -n filename; tail命令扩展 查看日志最后20行内容并实时更新日志 tail -f -n 20 server.log或者 tail -fn 20 ser…...
npm报错 Cannot find module ‘@vuepress\core\node_m
通常是由于缺少依赖包或者依赖包版本不兼容引起的。可以尝试以下步骤来解决这个问题: 确保您的项目的依赖包是最新的,可以运行 npm update 命令来更新依赖包。 如果更新依赖包后仍然有问题,可以尝试删除 node_modules 文件夹,并重…...

mybatis入门环境搭建及CRUD
一、MyBatis介绍 1.1 MyBatis的定义 MyBatis是一个开源的Java持久化框架,它可以帮助开发人员简化数据库访问的过程。它提供了一种将SQL语句与Java代码进行映射的方式,使得开发人员可以通过简单的配置文件来定义SQL语句,而无需编写繁琐的JDB…...
小程序变化历史记录
2023年8月26 小程序机号快速验证组件将需要付费使用 自2023年8月26日起,手机号快速验证组件将需要付费使用。标准单价为:每次组件调用成功,收费0.03元 https://blog.csdn.net/qq_37215621/article/details/131453551 自2023年9月1日起&…...

jstack(Stack Trace for Java)Java堆栈跟踪工具
jstack(Stack Trace for Java)Java堆栈跟踪工具 jstack(Stack Trace for Java)命令用于生成虚拟机当前时刻的线程快照(一般称为threaddump或者javacore文件)。 线程快照就是当前虚拟机内每一条线程正在执…...
linux面试题整理
目录标题 基础篇1.说下企业为什么用linux而不用windows?2.linux学过什么,怎么学习的?3.linux基本命令4.linux查看端口、进程、文件类型、挂载5.使用top命令之后前五行会显示什么内容?6.linux怎么查找一个文件7.vim进去后的各种操作…...

Linux笔记
Linux基础命令 Linux的目录结构 /,根目录是最顶级的目录了Linux只有一个顶级目录:/路径描述的层次关系同样适用/来表示/home/itheima/a.txt,表示根目录下的home文件夹内有itheima文件夹,内有a.txt ls命令 功能:列出…...

Dockerfile制作Web应用系统nginx镜像
目录 1.所需实现的具体内容 2.编写Dockerfile Dockerfile文件内容: 默认网页内容: 3.构建镜像 4.现在我们运行一个容器,查看我们的网页是否可访问 5.现在再将我们的镜像打包并上传到镜像仓库 1.所需实现的具体内容 基于centos基础镜像…...

lama-cleaner:基于SOTA AI 模型Stable Diffusion驱动的图像修复工具
介绍 由 SOTA AI 模型提供支持的图像修复工具。从照片中删除任何不需要的物体、缺陷、人物,或擦除并替换(由Stable Diffusion驱动)照片上的任何东西。 特征 1.多种SOTA AI模型 擦除模型:LaMa/LDM/ZITS/MAT/FcF/Manga 擦除和替…...

LVS-DR模式以及其中ARP问题
目录 LVS_DR LVS_DR数据包流向分析 LVS-DR中ARP问题 问题一 问题二 解决ARP的两个问题的设置方法 LVS-DR特点 LVS-DR优缺点 优点 缺点 LVS-DR集群构建 1.配置负载调度器 2.部署共享存储 3.配置节点服务器 4.测试 LVS 群集 LVS_DR LVS_DR数据包流向分析 客户端…...
2023-08-15 Untiy进阶 C#知识补充5——C#6主要功能与语法
文章目录 一、概述二、静态导入三、异常筛选器四、nameof 运算符 注意:在此仅提及 Unity 开发中会用到的一些功能和特性,对于不适合在 Unity 中使用的内容会忽略。 一、概述 C#6 的新增功能和语法主要包含: >运算符(C#…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...

MongoDB学习和应用(高效的非关系型数据库)
一丶 MongoDB简介 对于社交类软件的功能,我们需要对它的功能特点进行分析: 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具: mysql:关系型数据库&am…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...