首页 星云 工具 资源 星选 资讯 热门工具
:

PDF转图片 完全免费 小红书视频下载 无水印 抖音视频下载 无水印 数字星空

算法·理论:KMP 学习笔记

编程知识
2024年08月02日 19:59

\(\text{KMP}\) 笔记!

上次比赛,出题人出了一个 \(\text{KMP}\) 模板,我敲了个 \(\text{SAM}\) 跑了,但是学长给的好题中又有很多 \(\text{KMP}\),于是滚回来恶补字符串基本算法。

\(\text{KMP}\) 是上个寒假学的,为什么最近才完全理解,但 \(\text{KMP}\) 短小精悍,极其精简,确实难懂,所以很长一段时间都躲着它,最近突发灵感,遂写此篇。

前置知识:字符串基础字符串匹配(基本概念)

引入

\(\text{KMP}\) 算法,用于解决字符串匹配问题。这一类问题一般可以表述为「在主串 \(S\) 中查找模式串 \(T\) 的某些信息」。

显然我们有一种十分暴力的算法:枚举模式串 \(T\) 的起点,往后一位一位的比较。记 \(S\) 的长度为 \(n\)\(T\) 的长度为 \(m\),显然这种算法最坏是 \(O(nm)\) 的。

给出这种暴力的实现:

// force.cpp
int n,m;
char s[N],t[M];
void force(){
	for(int st=1;st+m-1<=n;st++){
		int i=st,j=1;
		while(j<=m&&s[i]==t[j]) i++,j++;
		if(j>m){
			// do something
		}
	}
}

当然我们可以用字符串哈希做到 \(O(n+m)\) 预处理,\(O(1)\) 比较两个字符串,复杂度变成 \(O(n+m)\)。实际上,这也是 \(\text{KMP}\) 的复杂度,但是 \(\text{KMP}\) 可以做到更多。

前缀函数-定义与性质

定义一个字符串 \(s\) 的前缀函数 \(nxt[i]\)\(s\) 长度为 \(i\) 的前缀 \(s[1\colon i]\)最长公共真前后缀的长度,为了方便用数组形式表式。

晕?不慌,看个例子。

比如说 \(s=\texttt{abcab}\),容易发现,\(\texttt{ab}\) 既是 \(s\) 的真前缀,又是 \(s\) 的真后缀,所以它是 \(s\)公共真前后缀,又发现 \(s\) 仅有 \(\texttt{ab}\) 一个公共真前后缀,所以 \(\texttt{ab}\) 自然是最长公共真前后缀,所以 \(s\)最长公共真前后缀的长度就等于 \(2\)

接下来,你能写出 \(\texttt{ababc}\)\(nxt[]\) 吗?

  • 对于 \(nxt[1]\),对应的前缀是 \(\texttt{a}\)最长公共真前后缀为空串(真前/后缀不算本身),于是 \(nxt[1]=0\)
  • 对于 \(nxt[2]\),对应的前缀是 \(\texttt{ab}\)最长公共真前后缀为空串,于是 \(nxt[2]=0\)
  • 对于 \(nxt[3]\),对应的前缀是 \(\texttt{aba}\)最长公共真前后缀\(\texttt{a}\),于是 \(nxt[3]=1\)
  • 对于 \(nxt[4]\),对应的前缀是 \(\texttt{abab}\)最长公共真前后缀\(\texttt{ab}\),于是 \(nxt[4]=2\)
  • 对于 \(nxt[5]\),对应的前缀是 \(\texttt{ababc}\)最长公共真前后缀为空串,于是 \(nxt[5]=0\)

综上,\(\texttt{ababc}\)\(nxt[]\)\(\{0,0,1,2,0\}\)

再来讲两个 \(nxt[]\) 数组的性质:

  • 性质 \(\bf{1}\)\(nxt[i]<i\),由定义得到。
  • 性质 \(\bf{2}\):设字符串 \(s\)\(p=\lvert s \rvert\),不断去做 \(p=nxt[p]\),出来的每个值即为原串的每个公共真前后缀的长度。(包括 \(nxt[p]\)\(nxt[nxt[p]]\)\(nxt[nxt[nxt[p]]]\)……)

性质 \(\bf{2}\) 证明

拿前两次来说,初始的 \(nxt[p]\)原串的每最长公共真前后缀的长度,所以 \(nxt[nxt[i]]\) 即为长度为 \(nxt[p]\) 的前缀的最长公共真前后缀的长度,记这个最长公共真前后缀\(u\),那么原串就有前缀 \(u\)

但又因为长度为 \(nxt[p]\) 的前缀等于长度为 \(nxt[p]\) 的后缀,所以长度为 \(nxt[p]\) 的后缀也有长度为 \(nxt[nxt[p]]\)最长公共真前后缀 \(u\),那么原串就也有后缀 \(u\)。所以原串有公共真前后缀 \(u\)

于是继续这样递归的理解一下,这样嵌套下去,每个值显然都是原串的公共真前后缀(把空串也理解为公共真前后缀)。

\(\bf{KMP}\)-匹配过程

想想怎么优化我们前文讲的 \(O(nm)\) 暴力。

比如说 \(S=\texttt{abababc}\)\(T=\texttt{ababc}\)

\(\texttt{\color{grey}{abababc}}\)
\(\texttt{\color{grey}{ababc}}\)

一开始,显然前四位都能匹配上:

\(\texttt{\color{green}{abab}\color{grey}{abc}}\)
\(\texttt{\color{green}{abab}\color{grey}{c}}\)

但到第五位,字符不同,这时我们称发生了一次失配

\(\texttt{\color{green}{abab}\color{red}{a}\color{grey}{bc}}\)
\(\texttt{\color{green}{abab}\color{red}{c}}\)

正常暴力时,我们需要将模式串往右移一位,全部重新匹配,像这样:

\(\texttt{\color{grey}{abababc}}\)
\(\texttt{ \color{grey}{ababc}}\)

然后继续比较:

\(\texttt{\color{grey}{a}\color{red}{b}\color{grey}{ababc}}\)
\(\texttt{ \color{red}{a}\color{grey}{babc}}\)

但是,显然有一种更加聪明的办法,由于模式串 \(T\) 已经匹配好了一段前缀 \(\texttt{abab}\),并且这段前缀中存在两段一样的字符 \(\texttt{ab|ab}\),所以后面一段 \(\texttt{ab}\) 匹配好的 \(S\) 的第三第四位可以直接给 \(T\) 的第一第二为用,并且直接从 \(T\) 的第三位为开始比较:

\(\texttt{\color{grey}{ab}\color{green}{ab}\color{grey}{abc}}\)
\(\texttt{\color{white}{--}\color{green}{ab}\color{grey}{abc}}\)

接着向后比较,匹配成功:

\(\texttt{\color{grey}{ab}\color{green}{ababc}}\)
\(\texttt{\color{white}{--}\color{green}{ababc}}\)

懂了又好像没懂?总而言之,我们的基本思想就是利用已经匹配了的部分和模式串 \(T\) 本身相同的部分进行优化。

已经匹配了的部分简单,但是现在问题就来了:什么样的 \(T\) 的相同部分可以被利用呢?怎么跳转呢?

先说结论:设当前 \(S[i+1] \neq T[j+1]\),即 \(S\)\(T\) 即将失配,那么接下来的最小可能匹配位置\(i-nxt[j]+1\)\(T\) 的开头位置),同时不需要移动 \(i\),直接 \(j\leftarrow nxt[j]\),然后继续比较 \(S[i+1] \neq T[j+1]\) 即可。

比如在上面的例子中,\(\texttt{ababc}\) 的匹配到 \(S[4]=T[4]\),但是在下一位 \(S[5] \neq T[5]\),也就是要失配了,所以我们 \(j\leftarrow nxt[j]\)\(j\leftarrow nxt[4]\)\(j\leftarrow 2\),于是继续比较 \(S[5]\)\(T[3]\) 即可。

证明

首先 \(i-nxt[i]+1\) 的正确性显然,就是利用 \(nxt[i]\) 提供的前后相等的信息,直接完成前 \(nxt[i]\) 位的匹配。

接着采用反证法证明 \(i-nxt[i]+1\)最小可能匹配位置。假设存在一个可能的匹配位置 \(1\lt p \lt i-nxt[j]+1\),如下图:

\(p\)\(j\) 的子串长为 \(len\),显然 \(len>nxt[i]\)。我们画出移动后的模式串 \(T\)(第三条橙色线),那么移动后第三条橙色线 \(T\) 的长为 \(len\) 的前缀等于第二条橙色线 \(p\)\(j\) 的子串即 \(T\) 长为 \(j\) 的前缀的长为 \(len\) 的后缀(上下对应)。

于是在长为 \(T\)\(j\) 的前缀中,长为 \(len\) 的前缀等于长为 \(len\) 的后缀,所以这个串是 \(T\)公共真前后缀,但是前面我们又说 \(len>nxt[i]\),这与 \(nxt[]\) 的定义矛盾,于是假设不成立,得证。

所以下一个可能的匹配位置就为 \(i-nxt[j]+1\),接着长度为 \(nxt[j]\) 的前缀,就可以利用我们前面匹配好的长度为 \(nxt[j]\) 的后缀匹配好,于是从 \((i-nxt[j]+1)+nxt[j]-1=i\) 继续匹配即可(相当于 \(i\) 不用改);至于 \(j\),由于前面 \(nxt[j]\) 为已经匹配好了,所以 \(j\leftarrow nxt[j]\) 即可。

那要是还失配呢?继续 \(j\leftarrow nxt[j]\) ,直到 \(S[i+1]=T[j+1]\)\(j=0\) 为止。

结合前面前缀函数 \(nxt[]\) 的性质感性理解一下:根据性质 \(\bf{2}\),这是一个找一遍每一个公共真前后缀的过程,根据 性质 \(\bf{1}\),每次操作后,长度不断减小,起始点就越近,这其实是一种不断 “退而求其次” 的思路,近一点就意味着更多的重复利用之前的匹配结结果,太近的匹配不上,就往后走,走太多了,那就会超出匹配过的范围,就没有可利用的结果了,那就不是当前的 \(i\) 下需要解决的问题了。

容易写成代码:

// kmp.cpp
int n,m,nxt[M];
char s[N],t[M];
void KMP(){
	// calculate nxt[]
	for(int i=1,j=0;i<=n;i++){
		while(j&&t[j+1]!=s[i]) j=nxt[j];
		j+=(t[j+1]==s[i]);
		if(j==m){
			// do something
		}
	}
} 

注意我们原来是说比较 \(S[i+1] \neq T[j+1]\),但是由于 \(i+1\) 的值在一轮循环中全程都不变,所以我们将 \(i\) 更新的工作交给循环提前做,我们在循环内部用 \(i\) 即可,不要写成 \(i+1\)

还有,为什么不是 j++ 呢?因为有可能根本就无法配对,所以要判断能不能匹配,匹配上了再 ++,即 j+=(t[j+1]==s[i]);

讲的很细了,应该代码没有什么问题,现在只剩下一个问题:怎么求前缀函数 \(nxt[]\)

前缀函数-求法

好吧,其实前缀函数 \(nxt[]\) 的求法才是 \(\text{KMP}\) 算法最常考的内容,甚至大部分的题都不需要匹配的过程,重点都在考查对前缀函数 \(nxt[]\) 的理解。

前缀函数的求法运用了增量法,即我们在已知前面的 \(nxt[]\) 时来确定新的函数值,当然也可以说是一种 dp。

设原串为 \(s\),接下来要求出 \(nxt[i]\),前面的所有 \(nxt[]\) 值已知,那么显然初始状态时是 \(nxt[1]=0\)

显然,若原串长这样:

\(\texttt{[aba]c}\cdots\texttt{[aba]}\)

其中被 \(\texttt{[ ]}\) 包裹的是最长公共真前后缀,那么这是分两种情况:

  • \(s[nxt[i-1]+1]=s[i]\) 时,即当加入 \(\texttt{c}\) 时,此时最长公共真前后缀变成 \(\texttt{[aba]c}\),即有 \(nxt[i]=nxt[i-1]+1\)
  • \(s[nxt[i-1]+1] \neq s[i]\),即加入一个不是 \(\texttt{c}\) 的字符时,那就无法与前面的最长公共真前后缀吻合上了,于是 “退而求其次”:最大不行,第二小的呢?相信你也想到了,就是利用前缀函数的性质 \(\bf{2}\),不断找更小的看看能不能吻合,找到最后,如果还没有,那么 \(nxt[i]=0\)

同样容易写成代码:

int n,m,nxt[M];
char s[N],t[M];
void KMP(){
	nxt[1]=0;
	for(int i=2,j=0;i<=m;i++){
		while(j&&t[j+1]!=t[i]) j=nxt[j];
		j=nxt[i]=j+(t[j+1]==t[i]);
	}
	for(int i=1,j=0;i<=n;i++){
		while(j&&t[j+1]!=s[i]) j=nxt[j];
		j+=(t[j+1]==s[i]);
		if(j==m){
			// do something
		}
	}
}

对比求前缀函数 \(nxt[]\) 的代码和匹配的代码,两份代码竟惊人的相似!

这是因为,设已经求出原串的一个前缀 \(s\) 的所有前缀函数,那么此时若再添加一个字符 \(c\),相当于是在 \((s+c)\) 中用 \(s\) 进行匹配的最后一轮的过程,只是我们不关心是否匹配好罢了,这个感性理解一下就好了。

\(\bf{KMP}\)-复杂度

我们分析前缀函数 \(nxt[]\) 的复杂度:

int m,nxt[M];
char t[M];
nxt[1]=0;
for(int i=2,j=0;i<=m;i++){
	while(j&&t[j+1]!=t[i]) j=nxt[j];
	j=nxt[i]=j+(t[j+1]==t[i]);
}

唯一有点迷的只有这个 while 了,其他都是 \(O(m)\) 的。

显然 while 中的语句是 \(O(1)\) 的,所以重点在于 while 的执行次数。

我们这么考虑,根据前缀函数的性质 \(\bf{1}\)\(j\)while 中每次至少减少 \(1\),但是 \(j\) 仅会在每次循环中加至多 \(1\),所以 \(j\) 的所有增加不会超过 \(m\),于是最多进入 while 循环 \(O(m)\) 次,于是总复杂度为 \(O(m)\)

匹配的复杂度分析类似,复杂度 \(O(n+m)\)

综上所述,\(\texttt{KMP}\) 算法的复杂度为 \(O(n+m)\)

容易构造出一种最坏情况,\(S=\texttt{aaa}\cdots\texttt{ab}\)\(T=\texttt{aaa}\cdots\texttt{a}\)

实际上,还有很多一般表现上 \(\text{KMP}\) 的字符串匹配算法,如 \(\text{BM}\)\(\text{Sunday}\) 等等,但是 \(\text{KMP}\)\(\text{OI}\) 中已经够用了,而且真正搞明白 \(\text{KMP}\) 也已经很不容易了呢~。

尾声

写完了!!!累!

本作品采用 CC BY-SA 4.0 进行许可,附加条款亦可使用。

From:https://www.cnblogs.com/godmoo/p/18339596
本文地址: http://www.shuzixingkong.net/article/724
0评论
提交 加载更多评论
其他文章 JavaScript 中的闭包和事件委托
包 (Closures) 闭包是 JavaScript 中一个非常强大的特性,它允许函数访问其外部作用域中的变量,即使在该函数被调用时,外部作用域已经执行完毕。闭包可以帮助我们实现数据的私有化、封装和模块化,使代码更简洁、易读和可维护。 闭包的定义 简单来说,闭包是指有权访问另一个函数作用域中变量的
万字干货:从消息流平台Serverless之路,看Serverless标准演进
摘要:如今,Serverless化已经成为消息流平台发展的新趋势,而如何更好地基于Serverless化的消息流平台进行应用设计和开发,则成为了一个值得思考的问题。 本文分享自华为云社区《9000字干货:从消息流平台Serverless之路,看Serverless标准演进》,作者:华为云PaaS服务
万字干货:从消息流平台Serverless之路,看Serverless标准演进 万字干货:从消息流平台Serverless之路,看Serverless标准演进 万字干货:从消息流平台Serverless之路,看Serverless标准演进
【VMware VCF】VMware Cloud Foundation Part 06:部署 VI 工作负载域。
VMware Cloud Foundation 标准架构中,管理域和 VI 工作负载域需要分开部署,管理域是初始构建(Bring-up)中部署的一个工作负载域并且只有一个,管理域专门用于承载管理相关组件虚拟机。之前文章(VMware Cloud Foundation Part 05:部署 SDDC
【VMware VCF】VMware Cloud Foundation Part 06:部署 VI 工作负载域。 【VMware VCF】VMware Cloud Foundation Part 06:部署 VI 工作负载域。 【VMware VCF】VMware Cloud Foundation Part 06:部署 VI 工作负载域。
ByteHouse高性能向量检索实践——“以图搜图”
ByteHouse 致力于实现全场景引擎覆盖,以确保实现整体数据效能的最大化产出。除了支持向量检索能力的Vector引擎,ByteHouse还具有全文检索引擎、GIS引擎在内的全场景引擎,为用户提供一体化数据分析服务。
ByteHouse高性能向量检索实践——“以图搜图” ByteHouse高性能向量检索实践——“以图搜图” ByteHouse高性能向量检索实践——“以图搜图”
告别痕迹:远程桌面连接历史和凭据的清零指南
本文指出在工作中运用 Windows 远程桌面工具时,因安全与隐私因素,有时需删除连接的历史记录和凭据。文中给出了一个相关的 PowerShell 脚本,还说明了其使用方法,涵盖运行 PowerShell 的条件、CredentialManager 模块的安装、脚本的执行流程及输入选择等,同时提到了
【Java】Jsoup 解析HTML报告
一、需求背景 有好几种报告文件,目前是人肉找报告信息填到Excel上生成统计信息 跟用户交流了下需求和提供的几个文件,发现都是html文件 其实所谓的报告的文件,就是一些本地可打开的静态资源,里面也有js、img等等 二、方案选型 前面老板一直说是文档解析,我寻思这不就是写爬虫吗.... 因为是在现
【Java】Jsoup 解析HTML报告 【Java】Jsoup 解析HTML报告 【Java】Jsoup 解析HTML报告
VirtualBox扩容CentOS-7虚拟机磁盘
1、背景描述 如上图所示,根路径“/”所在的文件系统已没有可用的磁盘空间,需要扩容磁盘。 df -h 2、VirtualBox操作 2.1、查看当前虚拟磁盘的大小 如上图所示,点击打开选中的虚拟机的 Settings 界面。 如上图所示,当前虚拟机的虚拟磁盘大小为 8GB 。 2.2、修改虚拟磁盘的
VirtualBox扩容CentOS-7虚拟机磁盘 VirtualBox扩容CentOS-7虚拟机磁盘 VirtualBox扩容CentOS-7虚拟机磁盘
代码随想录Day3
203.移除链表元素 给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。 示例 1: 输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5] 示例 2: 输入:hea
代码随想录Day3 代码随想录Day3