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#…...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error
在前端开发中,JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作(如 Promise、async/await 等),开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝(r…...
