当前位置: 首页 > news >正文

初识KMP算法

目录

1.KMP算法的介绍

2.next数组

3.总结


1.KMP算法的介绍

首先我们会疑惑,什么是KMP算法?这个算法是用来干什么的?

KMP(Knuth-Morris-Pratt)算法是一种用于字符串匹配的经典算法,它的目标是在一个主文本串(text)中查找一个模式串(pattern)的出现位置。KMP 算法通过利用模式串本身的特性,在匹配过程中避免回溯文本串的指针,从而达到快速匹配的目的。

KMP 算法的关键在于构建一个部分匹配表(Partial Match Table),

通常称为「next 数组」。这个表记录了模式串中每个位置对应的最长相同前缀后缀的长度。利用这个表,算法可以在匹配过程中智能地调整模式串的位置,避免不必要的比较,从而提高了匹配效率。

我们可以试想,当我们想将一个模式串遇主串匹配,并且找到模式串在主串中出现的第一个位置,通常我们会想到暴力求解。就是使用两个for循环,第一次for循环从主串的第一个元素开始遍历,当这时这个元素与模式串的第一个元素相同,那么我们就继续比对下一个元素,依次进行来找到模式串在主串出现的第一个元素,但是暴力求解的时间复杂度是(n*m),n是主串的长度,m是模式串的长度。

但是KMP算法可以将时间复杂度缩减到(n+m),大大节省了程序运行时间。

我们现在先来看一下KMP算法是如何匹配字符串,可以将时间复杂度缩减到(n+m)的。

面对上面这两个字符串的比对,我们会发现,在第一次比对时,只有最后一个元素不同,按照暴力算法是将子串与主串的第二个元素重新比对,但是KMP算法却不是这样比对,而是直接与主串的第三个元素比对,这时发现成功匹配。

那么我们应该怎么知道该将子串前进几个元素重新与主串比对呢?

这就需要我们引入一个next数组,前进几个元素取决于当出现不匹配的元素的前一个元素的所对应的next数组值。

2.next数组

1.构建部分匹配表(next 数组):遍历模式串,对每个位置计算最长相同前缀后缀的长度。这个长度表示了在当前位置失配时,应该移动模式串的位置以继续匹配。

那么什么是前后缀数组呢?

首先给出示例字符串:ababcbcab

它的前缀集合:{a,ab,aba,abab,ababc,ababcb,ababcbc,ababcbca}

它的后缀集合:{a,ab,cab,bcab,cbcab,bcbcab,abcbcab,babcbcab}

注意不能算是它本身,不然最长长度一直都是自己了。

看了上面的示例,那么对前后缀有了一个清晰的认识了吧!

这里相同的前后缀是ab,它的长度是2,那么此时的next数组里面是2。

现在给出求next数组的代码:

void get_next() //求出next数组 
{ int i=0,j=-1;next1[0]=-1;while(i<len2) if(j==-1 || s2[i]==s2[j]) next1[++i]=++j;else j=next1[j];
} 

我们现在给出一个示例字符串:ABABACAB

1.第1个元素直接是0。

2.第2个元素的前缀合集合是{A},后缀是{B},没有共同,第二个是0。

3.第3个元素的前缀合集合是{A,AB},后缀是{A,BA},有相同的"A",那么是1。

4.第4个元素的前缀合集合是{A,AB,ABA},后缀是{B,AB,BAB},相同的是"AB",那么是2。

5.第5个元素的前缀合集合是{A,AB,ABA,ABAB},后缀是{A,BA,ABA,BABA},相同的是"ABA",那么是3。

6.第6个元素的前缀合集合是{A,AB,ABA,ABAB,ABABA},后缀是{C,AC,BAC,ABAC,BABAC},没有相同的,那么是0。

7.第7个元素的前缀合集合是{A,AB,ABA,ABAB,ABABA,ABABAC},后缀是{A,CA,ACA,BACA,ABACA,BABACA},相同的是"A",那么是1。

8.第8个元素的前缀合集合是{A,AB,ABA,ABAB,ABABA,ABABAC,ABABACA},后缀是{B,AB,CAB,ACAB,BACAB,ABACAB,BABACAB},相同的是"AB",那么是2。

那么我们计算出的next数组是:0 0 1 2 3 0 1 2

现在我们看代码运行结果。

代码计算出来也与我们手算的结果一样。

3.总结

匹配过程:在主文本串中从左往右逐个字符地与模式串进行比较。当发生不匹配时,根据部分匹配表的值来移动模式串的位置,而不是直接回溯到起始位置重新开始比较。

这时我们看看KMP的核心代码:

void KMP() //KMP 
{ int i=0,j=0;//从第一个元素开始匹配 while(i<len1) { if(j==-1 || s1[i]==s2[j]) //匹配成功 i++,j++;else j=next1[j]; //失配 if(j==len2){cout<<i-len2+1<<endl;//此时i-len2+1为匹配成功的第一个元素位置 j=next1[j];//匹配成功,再失配 } }  
} 

总的来说,KMP 算法通过预处理模式串构建部分匹配表,然后利用这个表在匹配过程中避免不必要的回溯,从而提高了字符串匹配的效率。

下面我们可以做一道题来巩固我们的学习结果。

P3375 【模板】KMP - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

输入数据:

ABABABC
ABA

下面AC完整代码:

#include<bits/stdc++.h>
using namespace std;
int len1,len2;
int next1[1000001];
char s1[1000001];
char s2[1000001];
void get_next() //求出next数组 
{ int i=0,j=-1;next1[0]=-1;while(i<len2) if(j==-1 || s2[i]==s2[j]) next1[++i]=++j;else j=next1[j];
} 
void KMP() //KMP 
{ int i=0,j=0;//从第一个元素开始匹配 while(i<len1) { if(j==-1 || s1[i]==s2[j]) //匹配成功 i++,j++;else j=next1[j]; //失配 if(j==len2){cout<<i-len2+1<<endl;//此时i-len2+1为匹配成功的第一个元素位置 j=next1[j];//匹配成功,再失配 } }  
} 
int main(){ cin>>s1>>s2;len1=strlen(s1);len2=strlen(s2);get_next();KMP();for(int i=1;i<=len2;++i) cout<<next1[i]<<" ";//输出next数组 return 0;
}

相关文章:

初识KMP算法

目录 1.KMP算法的介绍 2.next数组 3.总结 1.KMP算法的介绍 首先我们会疑惑&#xff0c;什么是KMP算法&#xff1f;这个算法是用来干什么的&#xff1f; KMP&#xff08;Knuth-Morris-Pratt&#xff09;算法是一种用于字符串匹配的经典算法&#xff0c;它的目标是在一个主文本…...

Javaweb之SpringBootWeb案例之AOP概述及入门的详细解析

2.1 AOP概述 什么是AOP&#xff1f; AOP英文全称&#xff1a;Aspect Oriented Programming&#xff08;面向切面编程、面向方面编程&#xff09;&#xff0c;其实说白了&#xff0c;面向切面编程就是面向特定方法编程。 那什么又是面向方法编程呢&#xff0c;为什么又需要面向…...

【Java代码洁癖】NO.2 单元测试mock显式赋值,不能忍

反例 RunWith(MockitoJunitRunner.class) public class Test {Mockpublic SomeBean someBean new SomeBean(); } 正例 RunWith(MockitoJunitRunner.class) public class Test {Mockpublic SomeBean someBean ; } 解读 使用Mock注解的对象不应该被显式赋值&#xff0c;应当…...

2024.2.19

使用fread和fwrite完成两个文件的拷贝 #include<stdio.h> #include<stdlib.h> #include<string.h> int main(int argc, const char *argv[]) {FILE *fpNULL;if((fpfopen("./tset.txt","w"))NULL){perror("open error");retur…...

B端系统升级方案模板:针对美观性和体验性升级(总体方案)

大家好&#xff0c;我是大美B端工场&#xff0c;专注于前端开发和UI设计&#xff0c;有需求可以私信。本篇从全局分享如何升级B端系统&#xff0c;搞B端系统升级的有个整体思维&#xff0c;不是说美化几个图标&#xff0c;修改几个页面就能解决的&#xff0c;这个方案模板&…...

第九篇:node静态文件服务(中间件)

&#x1f3ac; 江城开朗的豌豆&#xff1a;个人主页 &#x1f525; 个人专栏 :《 VUE 》 《 javaScript 》 &#x1f4dd; 个人网站 :《 江城开朗的豌豆&#x1fadb; 》 ⛺️ 生活的理想&#xff0c;就是为了理想的生活 ! &#x1f4d8; 引言&#xff1a; 当今互联网时代&am…...

软件测试-功能测试-测试流程-如何进行需求评审?对于测试人员来讲,如何从测试的角度评审需求文档?

导言 产品人员编写的需求文档&#xff0c;无疑是一个项目或者一项新功能的开端。需求文档的优劣&#xff0c;直接影响开发人员的代码质量&#xff0c;更会影响到后续的测试工作。所以&#xff0c;我认为&#xff0c;需求评审对于开发质量以及测试质量至关重要&#xff0c;那么…...

无刷电机驱动详解

无刷电机驱动详解 有刷电机和无刷电机字面上理解最大的区别就是有无电刷&#xff0c;实际上区别还有换向器&#xff0c;电刷和换向器的作用是什么&#xff1f;电刷负责在旋转部件与静止部件之间传导电流&#xff0c;换向器则利用旋转惯性周期性的改变线圈中电流的方向。 所以…...

Linux+Win双系统远程重启到Win

背景 电脑安装了双系统&#xff08;ubuntu 22.04 win11&#xff09;&#xff0c;默认进入ubuntu系统。给电脑设置了WoL(Wake-on-LAN)&#xff0c;方便远程开机远程控制。 但是ubuntu的引导程序grub无法远程控制&#xff0c;远程开机会默认进入ubuntu。 虽然说可以进入ubuntu后…...

【XR806开发板试用】+移植rosserial到XR806

1 XR806简介 板子来源于极术社区的试用&#xff0c;XR806的在线网址 其主要参数&#xff1a; 主控XR806AF2LDDRSIP 288KB SRAM存储SIP 160KB Code ROM. SIP 16Mbit Flash.天线板载WiFi/BT双天线&#xff0c;可共存按键reboot按键 1&#xff0c;功能按键 1灯红色电源指示灯 1…...

JSON协议详解、语法及应用

文章目录 一、什么是JSON二、JSON协议结构协议结构包括要素JSON语法规则JSON的协议结构示例 三、JSON的特点四、JSON常见应用场景 一、什么是JSON JSON&#xff08;JavaScript Object Notation&#xff09;是一种轻量级的数据交换格式&#xff0c;它以易于阅读和编写的文本格式…...

kubeasz部署k8s:v1.27.5集群

安装k8s集群相关系统及组件的详细版本号 Ubuntu 22.04.3 LTS k8s: v1.27.5 containerd: 1.6.23 etcd: v3.5.9 coredns: 1.11.1 calico: v3.24.6 安装步骤清单&#xff1a; 1.deploy机器做好对所有k8s node节点的免密登陆操作 2.deploy机器安装好python2版本以及pip&#xff0c;…...

RSA加密,解密,加签及验签

目录 1.说明 2.加密和加签的区别 3.后端加密&#xff0c;解密&#xff0c;加签及验签示例 4.前端加密&#xff0c;解密&#xff0c;加签及验签示例 5.前端加密&#xff0c;后端解密&#xff0c;前端加签&#xff0c;后端验签 6.注意事项 1.说明 RSA算法是一种非对称加密…...

【C++搜索】BFS:走迷宫

题目描述 一个迷宫由R行C列格子组成&#xff0c;有的格子里有障碍物&#xff0c;不能走&#xff1b;有的格子是空地&#xff0c;可以走。 给定一个迷宫&#xff0c;求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走&#xff0c;不能斜着…...

SpringMVC 的参数绑定之list集合、Map

标签中name属性的值就是pojo类的属性名 参数绑定4 list [对象] <form action"teaupd.do" method"post"> <c:forEach items"${list}" var"tea" varStatus "status"> 教师编号&#xff1a;<input…...

Code Composer Studio (CCS) - Current and Local Revision

Code Composer Studio [CCS] - Current and Local Revision References 鼠标放在文件内的任意位置&#xff0c;鼠标右键 -> Compare With -> Local History -> Revision Time. References [1] Yongqiang Cheng, https://yongqiang.blog.csdn.net/...

Vue实现多个input输入,光标自动聚焦到下一个input

遇到一个需求&#xff0c;需要实现和移动端短信输入一样&#xff0c;输入内容后&#xff0c;光标会进入下一个输入框 需要用到2个事件 keydown事件发生在键盘的键被按下的时候 keyup 事件在按键被释放的时候触发 <template><div class"box"><el-fo…...

人工智能技术应用笔记(二):OpenAI SORA文生视频模型技术报告全文中英对照 (GPT4翻译+人工润色)

目录 Video generation models as world simulators&#xff08;视频生成模型作为世界模拟器&#xff09; Turning visual data into patches &#xff08;将视觉数据转换为图像块&#xff09; Video compression network &#xff08;视频压缩网络&#xff09; Spacetim…...

Linux-系统资源管理的命令

目录 查看CPU&#xff1a;more /proc/meminfo 查看内存数据&#xff1a;free -m / free -h 查看系统版本&#xff1a;more /etc/issue 查看操作系统的类型&#xff1a;uname -a 查看主机名称&#xff1a;hostname 查看磁盘空间&#xff1a;df -h 查看某个目录空间…...

Html的<figure><figcaption>标签

Html的<figure><figcaption>标签 示例一: <figure><figcaption>figcaption001, fig标题1 </figcaption><figcaption>figcaption002, fig标题2 </figcaption><div style"width:calc(100px*2); height:calc(100px*2); back…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】

微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来&#xff0c;Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...