「字符串」前缀函数|KMP匹配:规范化next数组 / LeetCode 28(C++)

概述

为什么大家总觉得KMP难?难的根本就不是这个算法本身。

在互联网上你可以见到八十种KMP算法的next数组定义和模式串回滚策略,把一切都懂得特别混乱。很多时候初学者的难点根本不在于这个算法本身,而是它令人痛苦的百花齐放的定义。

有的next数组从0下标开始,有的从1开始;有的表示不包括本字符的前面部分的真前后缀,有的表示包括本字符的的前后缀,有的回滚+1,有的不+1,而他们却总是忽略这些异同,自顾自地讲KMP的匹配问题。初学者看到这直接傻了眼:随便挑两个视频或者文章,他们的定义和递推手段都不一样,让理解难度雪上加霜。

下面我们来先从字符串匹配讲起,想一想什么样的next数组定义才最适合这个算法本身。

LeetCode 28:

给你两个字符串 haystack 和 needle ,请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标(下标从 0 开始)。如果 needle 不是 haystack 的一部分,则返回  -1 

示例 :

输入:haystack = "sadbutsad", needle = "sad"
输出:0
解释:"sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ,所以返回 0 。

*注意*: 接下来我们将称呼haystack为主串,needle为模式串。

思路 

最普通的暴力算法总是在匹配失败后将主串指针i回滚到开始匹配的位置,模式串指针j回滚到0,然后在一轮for循环结束后执行i++操作来跳过这个匹配失败的位置。来看看Code。

class Solution {
public:int strStr(string haystack, string needle) {const int n=haystack.size();const int m=needle.size();for(int i=0;i<n;i++){if(haystack[i]==needle[0])for(int k=i,j=0;k<n;k++){if(haystack[k]==needle[j])j++;else break;if(j==m)return i;}}return -1;}
};

来想一想:都回滚j了,为什么还回滚i?难道就因为有一个字符匹配失败了就放弃前面所有的努力吗?

至少在最后的失败字符之前,我们匹配成功了。这意味着:

模式串为pattern,主串为mainj
pattern[j]  a  b  c  a  b  f  g√  √  √  √  √  ×main[i]  a  b  c  a  b  k  v  q  x  ti

至少在'f'字符与'k'字符对比之前,我们的匹配成功了。

这意味着,main函数的此前部分和pattern的此前部分一一对应,我们称之为str1。

这时候的一个独到之处就是:

在这段主串和模式串共同的[开头,失配位置)的子串str1中,匹配失败之前的任意位置,从这个位置开始,一直到匹配失败的位置之前他们都相同,这部分[任意位置,失配位置)的子串我们称为str2

那我们可以有一个特殊的回滚模式串指针j的手段:不回滚到最开头,而是回滚到模式串的某个位置,在这个位置以前的部分模式串[开头,某位置)称为str3,它与str2相同。

结合例子感受一下:

模式串为pattern,主串为main┌str3┐ j<-------j
pattern[j] |a  b  c  a  b |f  g|        └str2┘| |√  √  √  √  √ ||        ┌str2┑|main[i] |a  b  c  a  b |k  v  q  x  t└----str1------┘i

这样看还是不够清晰,我们把j的移动形象理解成模式串的移动。

模式串为pattern,主串为main┌str3┐ j<-------j
pattern[j]           a  b  c  a  b  f  g└str2┘ √  √┌str2┑main[i]  a  b  c  a  b  k  v  q  x  t└----str1-----┘ i

也就是说:在j倒退回某个位置后,这位置之前的模式串部分和主串部分是天生匹配的。

接下来我会用前后缀的语言代替“某某部分”:

//这是对前后缀的解释,如果你了解,可以跳过
对于一个字符串
begin                enda b a c d x f a c a d---->           ---->前缀             后缀    //*注意*:前后缀的字符顺序都是从前向后
前缀是从[begin,x]的任意子字符串 真前缀的x不等于end
后缀是从 [x,end] 的任意子字符串 真后缀的x不等于begin

归纳一下

当匹配到主串i位置和模式串j位置,匹配失败时:

str2既是主串的[0,i)子串的一个后缀,又是模式串的[0,j)子字符串的一个后缀。

str3则是模式串中[0,j)子串的某个前缀,这个前缀与str2这个后缀相等。

因此,模式串中的str3能与模式串中的str2匹配,就意味着模式串中的str3与主串中的str2与是天生匹配的。

形象理解:

           str3==str2
pattern -str3------str2-√√√√√√√√√√√√√√√×
main    -----------str2-↓
pattern           -str3------str2-√√√√√?
main    -----------str2-

那按理来说,这是一个模式串的自匹配问题:对于模式串的每个位置j,都有[0,j)子串,都要找到他们的最长相同真前后缀。

因此问题就转化成了:

枚举模式串的每个下标j,求成它的[0,j)子字符串的最长相同真前后缀,这样,当在任意位置匹配失败时,都可以知道j的回滚位置了,而i从不回滚。

核心概念:前缀函数

网络上各种奇异搞笑的next数组定义的根本来源是他们没搞懂前缀函数和next数组的区别。

前缀函数是一个独立的算法函数概念,next数组只是它针对于KMP算法的特化版本。

1.前缀函数

它写作π[i]或PM[i]

定义:

给定一个长度为n的字符串,其前缀函数被定义为一个长度为n的数组π[n](或:PM[n])。 其中π[i]的意义是字符串的[0,i]子字符串的最长相同真前后缀

故有:

           j  0 1 2 3 4 5 6
string str[j] a b c a b c dπ[j] 0 0 0 1 2 3 0

这是标准的前缀函数定义,他长度就是n,下标起始位置就是0,其他的任何一种next数组都是他的特化版本。

*注意*:我通常使用j来作为next数组和模式串的索引。

2.next数组

在KMP匹配算法中,π数组变成了next数组,有如下几种方案:

1.考研版本

①模式串、主串和next数组下标统一从1开始计数。[j]表示第j个字符处,而不是索引0代表第1个字符。next[0]值为-1。

②next[j]表示原字符串{s[1]...s[j-1]}的最长相同真前后缀长度,它记录在了next[j]。next[j]的值不包括第j个字符。

③回滚代码:j=next[j]+1。

例如上文的"abcabcd",如果当j=7失配时,next[j]==3,那么j会从4开始继续匹配,跳过了123。

           j  0  1  2  3  4  5  6  7
string str[j] n  a  b  c  a  b  c  dnext[j] -1 0  0  0  0  1  2  3  
//n通常储存字符串的长度信息。

*注意*:你还会见到next[0]=0,且next数组整体+1的版本,它是另一个考研版本,只是将回滚代码的+1操作融入了next数组中,回滚代码:j=next[j],此处不再赘述。 

2.竞赛版本

事实上,在竞赛或者各大算法平台,字符串下标仍然从0开始,我们要为这个原则服务。

①字符串下标仍然从0开始,但我们仍然期望next数组下标从1开始。即主串与模式串从0开始,next数组从1开始,next数组长度比模式串大1,后续你会发现这样做的好处。

②next[j]表示原字符串*前j个字符*的最长相同真前后缀长度,它记录在了next[j],这里发生了错位。(next[0]=0,这样当j=0时执行回滚不会发生溢出,next[1]=0,第一个字符没有真先后缀)。

③回滚代码:j=next[j]。next数组错位的目的就是避免回滚代码发生+1-1的问题,这样能有效规避溢出。

例如上文的"abcabcd" ,如果当j=6失配时,next[j]==3,那么j会从3开始继续匹配,跳过了012。

即:j在某处失配时,它前面有j个字符,且这j个字符最长相同前后缀长度len储存在了next[j],可以快速访问next[j]得到j的回滚位置,回滚后恰好跳过len个字符。(我们总是期望在一轮for循环后j指向一个有待下一轮循环商榷的位置,不论是j++还是j=next[j],都是这样的。)

           j  0  1  2  3  4  5  6  7
string str[j] a  b  c  a  b  c  d \0next[j]    0  0  0  1  2  3  0  

算法过程

*注意*:我们会以竞赛版本的KMP进行讲解。它稍微更改就可以变成考研版。(比如insert函数)

构建next数组

构建next数组才是KMP本身具有难度的地方。

推论:字符串增加一个字符,它的最长相同真前后缀至多+1。这个不起眼的推论是构建的核心。

但是我们可以将其总结为3点:

①next[0]=0,next[1]=0,这两个直接无视。随后发生for循环int i=1,j=0。

i向前探索;j即用于为next[i+1]赋值,又作为下标索引与向前探索的i遥相呼应:[0,j]与[i-j,i]匹配。

因此j同时代表着:[0,i]的公共前后缀长度数值,也是与i这个前方洗标呼应的后方下标。

记得我们的定义是:next[j]表示原字符串*前j个字符*的最长相同真前后缀长度,i+1这个值才是[0,i]字符串的字符个数,因此j为next[i+1]赋值。

②当pattern[i]!=pattern[j],即位置i与位置j字符不匹配,通过while循环回滚j,如果仍失配,继续回滚,一直到j==0。

这一点是KMP的精髓所在:我们一边构建next数组,一边利用next数组回滚j。

这听起来很不可思议,但是注意:next数组是从前向后构建的,而回滚是向前的。这说明:我们在利用已经构建起的next数组进行回滚,而不会发生某种奇怪的冲突。

但是为什么用next数组回滚j呢?还记得next数组是干什么用的吗?它就是指示:当失配时,请从这里再试一试。不一定非要模式串与主串匹配才有失配,模式串自匹配时前缀不等于后缀也叫失配。我们回滚j就是期望将j回滚到可能与pattern[i]匹配的位置。

如果一直到j==0还失败,那就意味着不存在相同前后缀,那么为next[i+1]=j(即赋0值也是合理的了)

③判断pattern[i]是否等于pattern[j]。

如果因为j与i成功匹配而脱离while循环,那么j++,因为我们的最长相同前后缀+1。

void get_next(string&pattern,vector<int>&next){next[0]=0,next[1]=0;const int m=pattern.size();for(int i=1,j=0;i<m;i++){while(j&&pattern[j]!=pattern[i])j=next[j];if(pattern[j]==pattern[i])j++;next[i+1]=j;//赋值发生在j++之后,所以此处不用+1}}

匹配过程

匹配过程与构建过程极其类似。

主要是以下三点:

①当main[i]!=pattern[j],即在此处失配时,通过while循环回滚j,如果仍失配,继续回滚,一直到j==0。

跳出while后判断main[i]是否等于pattern[j]。

由于脱离while要么是两者相等要么不相等但j==0,那么:
if为真意味着:两者匹配成功,j++,i++。(两者在一轮循环后分别指向有待下一轮循环商榷的位置。)

if为假意味着:这一步就是判断出现j等于0且仍无法匹配的状况,那么认为这个i终究无法匹配,j停滞在0,随后放弃i的当前位置,i自增。

③判断j==m,这意味着完全匹配,返回i-m+1。(注意这里有个+1的细节:一轮for循环结束之前i++还未发生)

for(int i=0,j=0;i<n;i++){while(j&&main[i]!=pattern[j])j=next[j];if(main[i]==pattern[j])j++;if(j==m)return i-m+1;
}
return -1;

复杂度 

时间复杂度:O(n+m)

空间复杂度:O(m)

n:主串长度

m:模式串长度

Code

class Solution {
public:void get_next(string&pattern,vector<int>&next){const int m=pattern.size();for(int i=1,j=0;i<m;i++){while(j&&pattern[j]!=pattern[i])j=next[j];if(pattern[j]==pattern[i])j++;next[i+1]=j;}}int strStr(string haystack, string needle) {const int n=haystack.size(),m=needle.size();vector<int>next(m+1,0);get_next(needle,next);for(int i=0,j=0;i<n;i++){while(j&&haystack[i]!=needle[j])j=next[j];if(haystack[i]==needle[j])j++;if(j==m)return i-m+1;}return -1;}
};

(如果你充分理解了本文,就会发现代码竟然如此直观) 。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/405168.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ee trade:黄金投资与股票投资的区别

黄金和股票&#xff0c; 是金融市场中两种常见的投资工具&#xff0c; 它们拥有截然不同的特点和风险&#xff0c; 了解它们的差异&#xff0c; 可以帮助投资者制定更合理的投资策略。 一、 投资性质&#xff1a; 避险与成长&#xff0c; 两种投资方向 黄金&#xff1a; 被视…

【C++】入门篇一

【C】入门篇一 一 .缺省参数1.缺省参数的概念2. 缺省参数分类 二. 函数重载1. 函数重载概念2.函数重载代码举例 三.引用1.引用的概念2. 引用特性3. 常引用4. 使用场景(1). 做参数(2). 做返回值 5. 传值、传引用效率比较6. 引用和指针的区别7.引用和指针的不同点 一 .缺省参数 …

如何将MySQL迁移到TiDB,完成无缝业务切换?

当 MySQL 数据库的单表数据量达到了亿级&#xff0c;会发生什么&#xff1f; 这个现象表示公司的业务上了一个台阶&#xff0c;随着数据量的增加&#xff0c;公司规模也进一步扩大了&#xff0c;是非常喜人的一个改变 &#xff0c;然而随之而来的其他变化&#xff0c;就没那么…

Python | Leetcode Python题解之第354题俄罗斯套娃信封问题

题目&#xff1a; 题解&#xff1a; class Solution:def maxEnvelopes(self, envelopes: List[List[int]]) -> int:if not envelopes:return 0n len(envelopes)envelopes.sort(keylambda x: (x[0], -x[1]))f [1] * nfor i in range(n):for j in range(i):if envelopes[j]…

全液冷服务器革命:CPU、内存、PCIe高效散热新方案

在国家十四五规划大力发展数字经济的背景下&#xff0c;数据中心作为算力的核心载体&#xff0c;其基础设施成为支撑数字经济的“数字底座”&#xff0c;但同时也面临巨大的碳排放压力。随着芯片与服务器功耗的上升&#xff0c;单机柜功率密度不断增大&#xff0c;传统风冷散热…

深度学习设计模式之享元设计模式

文章目录 前言一、介绍二、特点三、详细介绍1.核心组成2.代码示例3.优缺点优点缺点 4.使用场景 总结 前言 享元设计模式主要用于减少创建对象的数量&#xff0c;以减少内存占用&#xff0c;提高性能。 一、介绍 享元设计模式&#xff08;Flyweight Pattern&#xff09;是一种…

Hexo通过GitHub设置自定义域名

本身GitHub也是支持自定义域名的&#xff0c;本次教程将讲解如何使用GitHub自带的自定义域名解析。 1. GitHub设置 1.1 登录GitHub账号 登录GitHub账号&#xff0c;找到名称为 用户名.github.io的仓库&#xff0c;并点击进入。 1.2 进入Settings页面 点击如图的Settings按…

【体检】程序人生之健康检查,全身体检与预防疫苗,五大传染病普筛,基因检测等

程序员养生指南之 【体检】程序人生之健康检查&#xff0c;全身体检项目分类&#xff0c;五大传染病普筛&#xff0c;基因检测等 文章目录 一、全身体检与预防疫苗&#xff08;年检&#xff09;1、实验室检测&#xff1a;生化全套检查2、医技检查&#xff1a;辅助诊疗科室3、科…

python中使用gurobi遇到强不等式约束(只有大于或者小于而不是大于等于或者小于等于的形式)的解决办法

文章目录 情况分析与解决思路数学模型严格不等式约束转化后的约束形式带入具体的 ϵ \epsilon ϵ 值 python代码总结 情况分析与解决思路 在gurobi求解数学优化问题时&#xff0c;标准的约束形式通常是大于等于&#xff08; >&#xff09;或小于等于&#xff08;<&…

Linux:网络基础概念

网络发展 独立模式: 计算机之间相互独立; 网络互联: 多台计算机连接在一起, 完成数据共享; 局域网 LAN: 计算机数量更多了, 通过交换机和路由器连接在一起; 广域网 WAN: 将远隔千里的计算机都连在一起; 所谓 "局域网" 和 "广域网" 只是一个相对的概念. 比如…

如何使用DEV-C++做游戏?

我的B站视频做过关于python的小游戏开发&#xff0c;但很多小伙伴希望通过C做一些有趣的动画或游戏&#xff0c;该怎么实现呢&#xff1f; B站&#xff1a;bigbigli_大李 大家好&#xff0c;我是大李。 今天主要跟大家谈谈如何通过C做一些小游戏开发&#xff0c;这里我们就 使用…

【游戏】什么是摄影游戏(Photography Games)

“Photography games” 是指以摄影为主题或核心机制的电子游戏。这类游戏通常让玩家通过虚拟摄像头或相机捕捉游戏世界中的场景、人物、动物或物品。这些游戏可以有不同的玩法和目标&#xff0c;通常包括以下几种类型&#xff1a; 探索与拍摄&#xff1a;玩家在游戏世界中自由…

嵌入式学习Day36---Linux软件编程---网络编程

目录 一、TCP并发模型 1.1.阻塞IO 1.2.非阻塞IO 1.步骤 2.函数接口 3.实例 1.3.异步IO 1.步骤 2.函数接口 3.实例 1.4.多路复用IO 1.select 函数接口&#xff1a; 实例 2.poll 3.epoll 二、总结 一、TCP并发模型 1.1.阻塞IO CPU占用率低,等待资源时将任务挂…

如何查看Squid的DNS缓存

使用squidclient mgr:ipcache命令查看Squid的DNS缓存记录 如果squid端口不是3128, 需要指定端口号, squidclient -p {port} mgr:ipcache # squidclient mgr:ipcache ... IP Cache Statistics: ... IP Cache Contents:Hostname Flg lstref TTL N(b)…

【旭日x3派】部署官方yolov5全流程

地平线旭日x3派部署yolov5--全流程 前言一、深度学习环境安装二、安装docker三、部署3.1、安装工具链镜像3.2、配置天工开物OpenExplorer工具包3.3、创建深度学习虚拟空间&#xff0c;安装依赖&#xff1a;3.4、下载yolov5项目源码并运行3.5、pytorch的pt模型文件转onnx3.6、最…

vscode提升:JSON 中不允许有注释

解决方案 &#xff1a; 运行&#xff1a; json with comment 参考链接&#xff1a; https://blog.csdn.net/eqizhihui/article/details/134014010 人工智能学习网站 https://chat.xutongbao.top

音视频相关知识

H.264编码格式 音频 PCM就是要把声音从模拟信号转换成数字信号的一种技术&#xff0c;他的原理简单地说就是利用一个固定的频率对模拟信号进行采样。 pcm是无损音频音频文件格式 每秒15帧 一秒钟300kb 单位&#xff1a;像素

K8S的统一访问入口-Service

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:Linux运维老纪的首页…

金山云Q2调整后EBITDA率提升至3.2% 高质量发展驱动经营质效双增

8月20日&#xff0c;金山云公布了2024年第二季度业绩。 季度内&#xff0c;金山云整体业绩延续向好态势&#xff0c;实现收入规模、盈利能力、经营现金流的联动共赢。财报显示&#xff0c;金山云Q2营收18.9亿元&#xff0c;公有云实现收入12.3亿元&#xff0c;行业云实现收入6…

GATK ReadLikelihoodCalculationEngine接口介绍

ReadLikelihoodCalculationEngine 是 GATK&#xff08;Genome Analysis Toolkit&#xff09;中的一个接口&#xff0c;用于计算不同等位基因&#xff08;haplotypes 或 alleles&#xff09;下的测序读数的似然值。这些似然值在变异检测过程中起着关键作用&#xff0c;帮助确定哪…