数据结构 “串“ 的补充提升与KMP算法及其优化的具体实现
❤️作者主页:微凉秋意
✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆
✨精品专栏:C++面向对象
🔥系列专栏:数据结构与课程设计
文章目录
- 🔥前言
- 串的基础知识
- 串的存储结构
- 顺序存储
- 链式存储
- 基本操作的实现
- 求子串
- 字符串比较
- 返回子串位置
- 字符串模式匹配
- 朴素模式匹配算法
- KMP 算法
- 求 next 数组(手算)
- next 数组优化为nextVal
🔥前言
今天补充数据结构专栏的文章,前阵子一直在准备考研,期间也是复习了很长时间的数据结构知识,对于一些结构也有了更深刻和独特的理解。今天就把有关 “串” 的基本操作以及比较热门的
KMP
算法做一个系统的总结,后期也会更新树、图以及考研热门算法的文章,建议大家订阅学习。
串的基础知识
先了解有关串的一些知识,方便以后遇到某些术语时能够心领神会。
串的定义:
串,即字符串(String
)是由零个或多个字符组成的有限序列,串中的字符个数n称为串的长度
。n = 0
时的串称为空串
串的术语:
子串:串中任意个连续的字符组成的子序列。
主串:包含子串的串。
字符在主串中的位置: 字符在串中的序号。
子串在主串中的位置:子串的第一个字符在主串的位置
比如:
S = ‘iPhone 11 Pro Max?’
‘iPhone’
和 'Pro M'
都是串 S 的子串,S 是子串‘iPhone’
的主串
'1'
在S 中的位置是8(第一次出现,下标从1
开始计算)
字符集编码:每个字符在计算机中对应一个二进制数,比较字符的大小其实就是比较二进制数的大小,这点在后续的字符串比较方法中会有体现。
串的存储结构
顺序存储
采用静态数组实现(定长顺序存储):
#define MAXLEN 255 //预定义最大串长为255
typedef struct{char ch[MAXLEN]; // 每个分量存储一个字符int length; // 串的实际长度
}SString;
采用动态数组实现(堆分配存储):
typedef struct {char* ch;int length;
}HString;// 初始化操作
HString S;
S.ch = (char*)malloc(MAXLEN * sizeof(char)); // 使用堆分配,使用过后需要手动 free 掉
S.length = 0;
在我们自己定义串的时候可以在
ch[0]
的位置存储串的长度,这样可以使字符的位序和数组的下标相同,但是要注意此时的长度取值范围仅在0~255
之内,这是char
类型能存储的最大长度。
链式存储
链式存储的形式一般都与单链表的存储形式一致,所以牢固掌握单链表很重要,有关文章在此专栏也有提供。
typedef struct StringNode {char ch; // 每个结点存一个字符struct StringNode* next;
}StringNode, *String;
如果每个结点只能存储一个字符,这样的数据结构的存储密度就太低了,因为 32 位操作系统下指针的大小为 4 个字节。因此可以适当的提高每个结点的存储容量,如:
typedef struct StringNode {char ch[8]; // 每个结点存多个字符struct StringNode* next;
}StringNode, *String;
顺序存储和链式存储的优缺点可以参考链表和顺序表的优缺点,从增删改查的效率上考虑即可。
基本操作的实现
这里采用顺序存储的方式来实现基本操作,即:
#define MAXLEN 255
typedef struct {char ch[MAXLEN];int length;
}SString;
另外,舍弃ch[0]
,从下标 1 开始存储字符。
求子串
对应方法:SubString(&Sub,S,pos,len)
:用Sub 返回串 S 的第pos 个字符起长度为 len 的子串
具体实现:
bool SubString(SString& Sub, SString S, int pos, int len) {if (pos + len - 1 > S.length) // 子串越界return false;for (int i = pos; i < pos + len; i++) {Sub.ch[i - pos + 1] = S.ch[i]; // 左边从下标 1 开始赋值}Sub.length = len;return true;
}
字符串比较
对应方法:StrCompare(S,T)
:若S>T,则返回值>0;若S=T,返回值=0,若小于,则返回值<0
具体实现:
int StrCompare(SString S, SString T) {for (int i = 1; i <= S.length && i <= T.length; i++) {if (S.ch[i] != T.ch[i]) // 如果不相等,直接用减法的结果当成比较结果return S.ch[i] - T.ch[i];}return S.length - T.length; // 此时比较字符串长度,用减法结果表示即可
}
返回子串位置
对应方法:Index(S,T)
:若主串S中存在与串T值相同的子串则返回他在主串中第一次出现的位置,否则返回0。
具体实现:
int Index(SString S, SString T) {SString P;for (int i = 1; i <= S.length - T.length + 1; i++) {SubString(P, S, i, T.length);if (StrCompare(P, T) == 0) {return i;}}return 0;
}
这里稍微的“偷懒”了一下,但是代码逻辑很清晰:
- P 串是主串 S 中长度为 T串长度的子串,赋值方法当然是通过调用之前写的获取子串方法
- 循环中 i 没必要走到主串的长度,只要 i 加上 T 的子串长度不大于 主串即可
- 调用字符串比较函数,只要P 与 T 相等,返回 i 值就是子串在主串中第一次出现的位置
字符串模式匹配
定义:在主串中找到与模式串相同的子串,并返回其所在位置。
两种算法:朴素模式匹配 与 KMP 算法
朴素模式匹配算法
这种方式可以称之为暴力解法:
- 我们从主串开始遍历,如果位序 1 不匹配,那么从2开始匹配;如果位序1至3都匹配,位序4不匹配,那么主串还是要从位序2继续匹配,而模式串回到位序1
- 因此每次的模式串都要从位序1遍历,而主串的位序会比上一次的位序多1
- 只要处理好主串的位序问题,那么就能暴力解题
具体算法:
int commonCompare(SString &s1, SString &s2) {int i,j;for (i = 1, j = 1; i <= s1.length,j <= s2.length;) {if (s1.ch[i] == s2.ch[j]) {i++, j++;}else {i = i - j + 2; // 理解此行代码很重要,此写法可以让位序逐渐加 1 j = 1;}if (j > s2.length)return i - s2.length;}return 0;
}
KMP 算法
KMP
算法比起朴素匹配算法多了一个重要的 next
数组,而且该数组与主串没有任何关系,我们需要通过模式串来求出 next
数组作为模式串指针指向的重要依据,而且主串的指针不回溯。
图示:
这里我们可以明显看到前四个字符都是匹配的,如果按照朴素模式匹配算法的逻辑,下一次主串指针会指向2,模式串指向1,重复朴素模式匹配操作;但实际上我们是可以知道主串前四个字符与模式串是对应的,因此不必让模式串指向1,而是将模式串向右 “移动”,如果模式串指向3,那说明前两个字符为a、b,这与主串a、a,并不对应,因此可以让模式串指向2,a 与 a 是对应的,那么下一步就是比较 b 与主串的第五个字符,时间效率提高了不少。
具体算法实现:
int Index_kmp(SString& S, SString& T, int next[]) {int i = 1, j = 1;while (i <= S.length && j <= T.length) {if (S.data[i] == T.data[j] || j == 0) {i++;j++;}else {j = next[j]; // 模式串的指向改变}if (j > T.length) {return i - T.length;}elsereturn 0;}
}
求 next 数组(手算)
上面也提到 next
数组是KMP
算法中的核心,因此一定要会手算该数组,其代表的也是当模式串在 j 位置不匹配时,下一步应该指向的位置:j = next[j]
。以下图为例:
如果第一个位置就不匹配,那就让 next[j] 的值为0,在写算法时如果 j 为0,那就让主串和模式串的指针都加1 即可;如果第二个位置不匹配,直接让 next[j] 为1,也就是让模式串的第一个和主串的第二个字符比较。以后写 next 数组时,指针1和2的位置分别无脑写0
和1
。
对于此例也是一样,现在看位序3失配时,next 该为多少:
主串与模式串前两个字符都是 a和b,显然模式串右移一位后a与b并不匹配,因此位序3的next 应为 1。
对于位序4:
前三个字符均为aba,因此模式串移动两位后的 a 可以与主串第三位对应,所以位序4的next应为2。
对于位序5:
右移两位后虽然 a 与 a 对应,但是随后的 b 与 a 不对应,所以其next 还是 2。
对于位序6:
模式串的 ab 与 主串的 ab 对应,因此其 next 为3。
即 next[7] = { ,0,1,1,2,2,3}
,next[0]舍弃不用。
next 数组优化为nextVal
KMP 算法的优化实际上也就是对next 数组的优化,优化思路如下:
比如第三个位序不匹配时,我们除了知道两者的前两个字符为 ab 外,其次可以知道主串的第三字符一定不是 a
,那么模式串的第一个字符 a 就没必要再去和主串的第三个字符比较了,直接让 next 的值为0,下一步主串和模式串的指针都加1。
其余位序也是以同样的思维得到,我算出的数组为:
nextVal[7] = { ,0,1,0,2,1,3}
给出对应的转换函数:
// 优化 next 为 nextVal
void optimize_next(int next[],int nextVal[],SString &T) {nextVal[1] = 0; // 无脑写0for (int j = 2; j <= T.length; j++) {// 字符相等,nextVal 的值应为前面字符对应的nextValif (T.ch[j] == T.ch[next[j]]) {nextVal[j] = nextVal[next[j]];}else {// 字符不等,无法优化,继承next数组的数据即可nextVal[j] = next[j];}}
}
那么到此 串 的知识、基本操作的实现、朴素匹配和KMP算法以及优化就总结完毕了,重点是掌握KMP算法中的手算 next
数组,大家可以自己找主串和模式串进行练习,彻底掌握 KMP 算法。
相关文章:

数据结构 “串“ 的补充提升与KMP算法及其优化的具体实现
❤️作者主页:微凉秋意 ✅作者简介:后端领域优质创作者🏆,CSDN内容合伙人🏆,阿里云专家博主🏆 ✨精品专栏:C面向对象 🔥系列专栏:数据结构与课程设计 文章目录…...
如何使用Spring Cloud搭建MQ(Message Queue)消息队列
Spring Cloud是一个开源框架,用于构建基于微服务架构的应用程序。它提供了多种工具和技术,用于实现各种微服务模式,并使它们易于管理和部署。MQ(消息队列)则是一种重要的异步通信机制,用于在不同的应用程序…...

iphone备忘录删除怎么恢复?分享苹果数据找回办法
手机备忘录上写记录,这是不少上班族的小习惯。因为它可以先记录紧急事务,然后再慢慢的解决。也可以把我们一些重要的账号密码存在备忘录里,方便在何时何地直接登入使用。那么如果我们不小心删除了iphone备忘录呢?碰到这种事该怎么办呢?有没…...

【PPT】《我去!还有这种网站?》-知识点目录
《我去!还有这种网站?》 1. Vega AI 输入提示: girl,粉头发2. 物理画线:休闲小游戏 3. Dialogue:影视台词搜索 4. Can you run it:游戏设备要求查询 5. Deviceshots:使用设备边…...
SQL 将查询结果插入到另一张表中
INSERT INTO (1) 如果两张表(导出表和目标表)的字段一致,并且希望插入全部数据,可以用这种方法: INSERT INTO 目标表 SELECT * FROM 来源表 WHERE 条件;例如,要将 test 表插入到 n…...

代码随想录算法训练营day48 | 动态规划 121 买卖股票的最佳时机 122 买卖股票的最佳时机II
day48121. 买卖股票的最佳时机1.确定dp数组(dp table)以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp数组122.买卖股票的最佳时机II121. 买卖股票的最佳时机 题目链接 解题思路: 动规五部曲分析如下:…...

MediaTek 天玑 8000 5G移动平台详细参数
MediaTek 天玑 8000 移动平台 采用先进的 台积电 5nm 工艺,拥有出众的性能和能效,为高端智能手机用户提供出色的高帧率游戏和 5G 移动体验。 天玑 8000 采用了 MediaTek 诸多先进技术,内置 MediaTek Imagiq 780影像引擎、第五代 AI 处理器APU…...

Kafka
这里写目录标题1.Kafka1.1 Kafka概述1.2 kafka安装和配置1.3 入门案例1.4 kafka生产者详解1.4.1 生产者的参数1.Kafka 1.1 Kafka概述 Kafka 是一个分布式流媒体平台,类似于消息队列或企业消息传递系统。 producer:发布消息的对象称之为主题生产者(Ka…...
数据结构——第三章 栈与队列(2)
栈的运用1.括号匹配2.表达式求值2.1.算术表示式的形式2.2.后缀表达式求值2.3.将算术表达式转换为后缀表达式2.4.算术表达式直接求值3.栈与递归3.1.递归算法3.2.栈与函数调用3.3.递归工作与递归函数3.4.递归到非递归的转换1.括号匹配 void matching(char str[]) {//创建空栈Lin…...

【Linux学习】基础IO——理解缓冲区 | 理解文件系统
🐱作者:一只大喵咪1201 🐱专栏:《Linux学习》 🔥格言:你只管努力,剩下的交给时间! 基础IO☕理解缓冲区🧃缓冲区的共识🧃缓冲区的位置🧃缓冲区的刷…...

RHCSA-重置root密码(3.3)
方法1:rd.break (1)首先重启系统,在此页面按e键,在屏幕上显示内核启动参数 (2)知道linux这行,末尾空格后输入rd.break,然后按ctrlx (3)查看&#…...

无公网IP快解析实现U+随时随地访问
现阶段商品从生产到消费者手中要经过多个环节,为实现对每一个环节进行管理,越来越多的企业选择通过信息化手段来实现。供应链管理系统配合供应链中各实体的业务需求,使操作流程和信息系统紧密配合,做到各环节无缝链接,…...
UVa 307 Sticks 木棍拼接 ID 迭代加深搜
题目链接:Sticks 题目描述: 小明一开始有一些长度相等的木棍,小明现在将木棍砍成了一些长度为整数的木棍,他现在忘记了最开始木棍的长度,你需要找到最短的可能木棍长度,例如给定5,2,1,5,2,1,5,2,15,2,1,5,2…...

阿里云(CentOS)中MySQL8忘记密码的解决方法
阿里云(CentOS)中MySQL8忘记密码的解决方法 方法 在 skip-grant-tables 模式下启动 MySQL,该模式下启动 MySQL 时不启动授权表功能,可以直接免密码登录 实现 编辑 /etc/my.cnf 文件 vim /etc/my.cnf在 [mysqld] 区域末尾添加配置,设置免密…...

三、Spring的入门程序
第一个Spring程序 创建新的空工程spring6 设置JDK版本17,编译器版本17 设置IDEA的Maven:关联自己的maven 在空的工程spring6中创建第一个maven模块:spring6-001-first 在pom.xml添加spring context依赖和junit依赖, <?x…...

摘录一下Python列表和元组的学习笔记
1 基础概念 列表一个值,列表值指的是列表本身,而不是列表中的内容 列表用[]表示 列表中的内容称为 表项 len()函数可以显示列表中表项的个数,比如下面这个例子 spam [cat, bat, dog, rat]print(len(spam))列表的范围选取中,比…...
【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤
【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤 1 收益率 在学术界,建模一般不直接使用资产价格,而是使用资产收益率(Returns)。因为收益率比价格具有更好的统计特性,更便于建模。下经典…...

1_机器学习概述—全流程
文章目录1 机器学习定义2 机器学习常见应用框架(重点)3 机器学习分类3.1 监督学习(Supervised learning)3.2 无监督学习(Unsupervised learning)3.3 半监督学习(Semi-Supervised Learning&#…...

VUE中给对象添加新属性时,界面不刷新怎么办
一、直接添加属性的问题 举例: 定义一个p标签,通过v-for指令进行遍历 然后给botton标签绑定点击事件,我们预期点击按钮时,数据新增一个属性,界面也 新增一行。 <p v-for"(value,key) in item" :key&qu…...

视频号频出10w+,近期爆红的账号有哪些?
回顾2月,视频号持续放出大动作,不仅进行了16小时不间断的NBA全明星直播,还邀请国际奥委会入驻,分享奥运的最新资讯。视频号成为越来越多官方机构宣传推广的有效渠道。官方积极入驻,内容创作生态也在同步繁荣发展&#…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...

select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...

uniapp 小程序 学习(一)
利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 :开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置,将微信开发者工具放入到Hbuilder中, 打开后出现 如下 bug 解…...

恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...

从零开始了解数据采集(二十八)——制造业数字孪生
近年来,我国的工业领域正经历一场前所未有的数字化变革,从“双碳目标”到工业互联网平台的推广,国家政策和市场需求共同推动了制造业的升级。在这场变革中,数字孪生技术成为备受关注的关键工具,它不仅让企业“看见”设…...