当前位置: 首页 > 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…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

ubuntu22.04有线网络无法连接,图标也没了

今天突然无法有线网络无法连接任何设备&#xff0c;并且图标都没了 错误案例 往上一顿搜索&#xff0c;试了很多博客都不行&#xff0c;比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动&#xff0c;重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...

车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇

我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...