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

数据结构 “串“ 的补充提升与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 数组作为模式串指针指向的重要依据,而且主串的指针不回溯。

图示:
KMP

这里我们可以明显看到前四个字符都是匹配的,如果按照朴素模式匹配算法的逻辑,下一次主串指针会指向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]。以下图为例:

求 nxet数组
如果第一个位置就不匹配,那就让 next[j] 的值为0,在写算法时如果 j 为0,那就让主串和模式串的指针都加1 即可;如果第二个位置不匹配,直接让 next[j] 为1,也就是让模式串的第一个和主串的第二个字符比较。以后写 next 数组时,指针1和2的位置分别无脑写01

对于此例也是一样,现在看位序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 数组的优化,优化思路如下:

求 nxet数组
比如第三个位序不匹配时,我们除了知道两者的前两个字符为 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算法及其优化的具体实现

❤️作者主页&#xff1a;微凉秋意 ✅作者简介&#xff1a;后端领域优质创作者&#x1f3c6;&#xff0c;CSDN内容合伙人&#x1f3c6;&#xff0c;阿里云专家博主&#x1f3c6; ✨精品专栏&#xff1a;C面向对象 &#x1f525;系列专栏&#xff1a;数据结构与课程设计 文章目录…...

如何使用Spring Cloud搭建MQ(Message Queue)消息队列

Spring Cloud是一个开源框架&#xff0c;用于构建基于微服务架构的应用程序。它提供了多种工具和技术&#xff0c;用于实现各种微服务模式&#xff0c;并使它们易于管理和部署。MQ&#xff08;消息队列&#xff09;则是一种重要的异步通信机制&#xff0c;用于在不同的应用程序…...

iphone备忘录删除怎么恢复?分享苹果数据找回办法

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

【PPT】《我去!还有这种网站?》-知识点目录

《我去&#xff01;还有这种网站&#xff1f;》 1. Vega AI 输入提示&#xff1a; girl&#xff0c;粉头发2. 物理画线&#xff1a;休闲小游戏 3. Dialogue&#xff1a;影视台词搜索 4. Can you run it&#xff1a;游戏设备要求查询 5. Deviceshots&#xff1a;使用设备边…...

SQL 将查询结果插入到另一张表中

INSERT INTO &#xff08;1&#xff09; 如果两张表&#xff08;导出表和目标表&#xff09;的字段一致&#xff0c;并且希望插入全部数据&#xff0c;可以用这种方法&#xff1a; INSERT INTO 目标表 SELECT * FROM 来源表 WHERE 条件;例如&#xff0c;要将 test 表插入到 n…...

代码随想录算法训练营day48 | 动态规划 121 买卖股票的最佳时机 122 买卖股票的最佳时机II

day48121. 买卖股票的最佳时机1.确定dp数组&#xff08;dp table&#xff09;以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp数组122.买卖股票的最佳时机II121. 买卖股票的最佳时机 题目链接 解题思路&#xff1a; 动规五部曲分析如下&#xff1a…...

MediaTek 天玑 8000 5G移动平台详细参数

MediaTek 天玑 8000 移动平台 采用先进的 台积电 5nm 工艺&#xff0c;拥有出众的性能和能效&#xff0c;为高端智能手机用户提供出色的高帧率游戏和 5G 移动体验。 天玑 8000 采用了 MediaTek 诸多先进技术&#xff0c;内置 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&#xff1a;发布消息的对象称之为主题生产者&#xff08;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——理解缓冲区 | 理解文件系统

&#x1f431;作者&#xff1a;一只大喵咪1201 &#x1f431;专栏&#xff1a;《Linux学习》 &#x1f525;格言&#xff1a;你只管努力&#xff0c;剩下的交给时间&#xff01; 基础IO☕理解缓冲区&#x1f9c3;缓冲区的共识&#x1f9c3;缓冲区的位置&#x1f9c3;缓冲区的刷…...

RHCSA-重置root密码(3.3)

方法1&#xff1a;rd.break &#xff08;1&#xff09;首先重启系统&#xff0c;在此页面按e键&#xff0c;在屏幕上显示内核启动参数 &#xff08;2&#xff09;知道linux这行&#xff0c;末尾空格后输入rd.break&#xff0c;然后按ctrlx &#xff08;3&#xff09;查看&#…...

无公网IP快解析实现U+随时随地访问

现阶段商品从生产到消费者手中要经过多个环节&#xff0c;为实现对每一个环节进行管理&#xff0c;越来越多的企业选择通过信息化手段来实现。供应链管理系统配合供应链中各实体的业务需求&#xff0c;使操作流程和信息系统紧密配合&#xff0c;做到各环节无缝链接&#xff0c;…...

UVa 307 Sticks 木棍拼接 ID 迭代加深搜

题目链接&#xff1a;Sticks 题目描述&#xff1a; 小明一开始有一些长度相等的木棍&#xff0c;小明现在将木棍砍成了一些长度为整数的木棍&#xff0c;他现在忘记了最开始木棍的长度&#xff0c;你需要找到最短的可能木棍长度&#xff0c;例如给定5,2,1,5,2,1,5,2,15,2,1,5,2…...

阿里云(CentOS)中MySQL8忘记密码的解决方法

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

三、Spring的入门程序

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

摘录一下Python列表和元组的学习笔记

1 基础概念 列表一个值&#xff0c;列表值指的是列表本身&#xff0c;而不是列表中的内容 列表用[]表示 列表中的内容称为 表项 len()函数可以显示列表中表项的个数&#xff0c;比如下面这个例子 spam [cat, bat, dog, rat]print(len(spam))列表的范围选取中&#xff0c;比…...

【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤

【量化金融】收益率、对数收益率、年华收益、波动率、夏普比率、索提诺比率、阿尔法和贝塔、最大回撤 1 收益率 在学术界&#xff0c;建模一般不直接使用资产价格&#xff0c;而是使用资产收益率(Returns)。因为收益率比价格具有更好的统计特性&#xff0c;更便于建模。下经典…...

1_机器学习概述—全流程

文章目录1 机器学习定义2 机器学习常见应用框架&#xff08;重点&#xff09;3 机器学习分类3.1 监督学习&#xff08;Supervised learning&#xff09;3.2 无监督学习&#xff08;Unsupervised learning&#xff09;3.3 半监督学习&#xff08;Semi-Supervised Learning&#…...

VUE中给对象添加新属性时,界面不刷新怎么办

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

视频号频出10w+,近期爆红的账号有哪些?

回顾2月&#xff0c;视频号持续放出大动作&#xff0c;不仅进行了16小时不间断的NBA全明星直播&#xff0c;还邀请国际奥委会入驻&#xff0c;分享奥运的最新资讯。视频号成为越来越多官方机构宣传推广的有效渠道。官方积极入驻&#xff0c;内容创作生态也在同步繁荣发展&#…...

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

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

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

select、poll、epoll 与 Reactor 模式

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

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; 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&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

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

uniapp 小程序 学习(一)

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

恶补电源:1.电桥

一、元器件的选择 搜索并选择电桥&#xff0c;再multisim中选择FWB&#xff0c;就有各种型号的电桥: 电桥是用来干嘛的呢&#xff1f; 它是一个由四个二极管搭成的“桥梁”形状的电路&#xff0c;用来把交流电&#xff08;AC&#xff09;变成直流电&#xff08;DC&#xff09;。…...

从零开始了解数据采集(二十八)——制造业数字孪生

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