数据结构与算法基础(王卓)(16):KMP算法详解(代码实现)
实现代码的过程中
具体细节、问题:
(1):关于写Get_next函数的标题:
现象:
PPT上写的是:
void get_next(SString T, int &next[])
然而并不能运行,而当我们去掉了引用符号(&)以后:
void get_next(SString T, int next[])
却可以运行,但是这里引用的符号就代表着把数据传回(给)主函数,所以最好不要省略
//&:返回所有我们算出的next[]
原因:
数组不能采用引用格式来传值
根本不存在“元素都是引用的数组”:
本身数组就是用他的首地址来传值的,其首地址代表一大串数组的信息和地址(位置)
而引用传值只是给变量取了一个别名来传值,自然不能无法整个数组的值
总得来说就是一个格式的问题
(2):关于Get_next函数中k的初值:
int j = 0,//从头开始算起k = -1;next[0] = -1;//根据公式
一开始我们想令 k = 0; ,后面真的想去运行以后发现不可以:
根据公式和算法设计,即使是MAX[k]也必须要小于j
(3):关于KMP函数里,next数组赋初值 和 调用Get_next函数的语句的问题:
不同版本不同教材的不同写法:
网课(PPT):
int i = pos, j = 1;
没有给next数组赋初值
也没有调用Get_next函数
啥也没有,主打的就是一个陪伴
乐
这样是肯定不行的:

书上:
int next[MAXLEN];int i = pos, j = 1;Get_next(T, next);
给next数组赋初值
调用Get_next函数,但是里面写的是next而非next[]
结果:


把书上的改进为:
给next数组赋初值
调用Get_next函数,并且写next[]
int next[MAXLEN];int i = pos, j = 1;Get_next(T, next[]);
结果也不行:

到这里,我们似乎已经山穷水尽,走投无路了
这个时候多和同学沟通交流就成了关键,于是我们又有了如下进展,这也是我们最终最重要的
问题(3)的收获:
(1):首先:
给next数组赋初值不能少毋庸置疑,没有可能说有那个变量能够不赋初值就直接进行运算操作的
所以PPT上的情况肯定是不行的(差评)
(2):对于书上写的这种情况:
如果我们不要这个Get_next函数的引用符号(不再采用引用传值)
采用实参形参传值,即将其定义的抬头改为:
void Get_next(SString T, int next[])
程序即可成功正确运行:(完整程序如下)这也正是我们
用next最终实现KMP算法的结果:
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit
#include<math.h>//OVERFLOW,exittypedef int Status;
#define MAXLEN 255struct SString//Sequence String
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度长度
};void Get_next(SString T, int next[])
//给你一个子串T,教你逐个算出每个位序对应的next[]
{int j = 0,//从头开始算起k = -1;next[0] = -1;//根据公式while (j <= T.length - 1)//因为位序从0(而非1)开始{if (k == -1 || T.ch[k] == T.ch[j]){j++;k++;next[j] = k;}elsek = next[k];}
}int Index_KMP(SString S, SString T, int pos)
{int next[MAXLEN];Get_next(T, next);int i = pos, j = 1;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j]){++i; ++j;}//主串和子串依次匹配下一个字符elsej = next[j];}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;
}int main()
{}
同样的,我们不采用引用,我们也还可以采用地址传值,将其定义Get_next的抬头改为:
void Get_next(SString T, int *next)
程序即可成功正确运行:(完整程序如下)
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit
#include<math.h>//OVERFLOW,exittypedef int Status;
#define MAXLEN 255struct SString//Sequence String
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度长度
};void Get_next(SString T, int *next)
//给你一个子串T,教你逐个算出每个位序对应的next[]
{int j = 0,//从头开始算起k = -1;next[0] = -1;//根据公式while (j <= T.length - 1)//因为位序从0(而非1)开始{if (k == -1 || T.ch[k] == T.ch[j]){j++;k++;next[j] = k;}elsek = next[k];}
}int Index_KMP(SString S, SString T, int pos)
{int next[MAXLEN];Get_next(T, next);int i = pos, j = 1;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j]){++i; ++j;}//主串和子串依次匹配下一个字符elsej = next[j];}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;
}int main()
{}
为什么不能使用引用:
其实原因我们可能意想不到,在前面的问题(1)当中其实就已经有能解释该现象原因的解答了:
数组不能采用引用格式来传值
根本不存在“元素都是引用的数组”:
本身数组就是用他的首地址来传值的,其首地址代表一大串数组的信息和地址(位置)
而引用传值只是给变量取了一个别名来传值,自然不能(无法)传递整个数组的值
所以只要我们不用引用传数组,自然不会出问题
然而的虽然得到了标准答案,我们还有新的问题没有解决:
(4):传值问题(小结)
根据同学提醒,这里其实我们很有必要举一反三,重新温习一下
如果想要通过调用函数功能传达改变的值,除了数组以外的变量,不要用形参实参传值
否则会产生最后数值没变的结果
(5):为什么地址(指针)传值的时候及调用函数的时候不能写next[]
next 既代表整个数组,也代表这个数组的头指针
地址传值:
next 前面已经加了 * 符号,再加 [ ] 就相当于要求接收**next类型的实参数据了,显然不符合我们的出发点
调用函数:
这方面其实我也不是很确定:
显然从设计程序的角度而言,我们清楚地知道这个位置需要的是一个数组的首地址,也就是这个数组的头指针
(我觉得)因为next[]无法代表这个数组的首地址,而直接写数组的名称next肯定是鞥狗代表整个数组(也包括首地址)的
另外,我觉得一定要写出next[]形式的首地址的话,其形式效果相当于:&next[0]

(6):调用Get_next函数是否必要
理论上应该是没有调用数据就传不进去,具体有待验证
(7):else语句当中BF算法的语句是什么?
k--?
待解决
PART 2:关于nextval[ j ]
以后再写,答案:
#include<iostream>
using namespace std;
#include<stdlib.h>//存放exit
#include<math.h>//OVERFLOW,exittypedef int Status;
#define MAXLEN 255struct SString//Sequence String
{char ch[MAXLEN + 1]; //存储串的一维数组int length; //串的当前长度长度
};void Get_nextval(SString T, int nextval[])
//给你一个子串T,教你逐个算出每个位序对应的next[]
{int j = 0,//从头开始算起k = -1;nextval[0] = -1;//根据公式while (j <= T.length){if (k == -1 || T.ch[k] == T.ch[j]){j++;k++;if (T.ch[k] != T.ch[j])nextval[j] = k;elsenextval[j] = nextval[k];}elsek = nextval[k];}
}int Index_KMP(SString S, SString T, int pos)
{int nextval[MAXLEN];Get_nextval(T, nextval);int i = pos, j = 1;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j]){++i; ++j;}//主串和子串依次匹配下一个字符elsej = nextval[j];}if (j > T.length)return i - T.length; //匹配成功elsereturn false;
}int main()
{}
相关文章:
数据结构与算法基础(王卓)(16):KMP算法详解(代码实现)
实现代码的过程中 具体细节、问题: (1):关于写Get_next函数的标题: 现象: PPT上写的是: void get_next(SString T, int &next[]) 然而并不能运行,而当我们去掉了引用符号&…...
九龙证券|盘前直接腰斩,银行巨头紧急“拔网线”!美股银行股又崩了?
见证历史了,又有一家银行巨子倒下? 美股银行股团体暴降 上一交易日暴降超60%的硅谷银行持续面对腥风血雨。盘前,硅谷银行跌幅超50%,随后,公司宣布盘前暂停交易,等待刊发消息。 而最新消息显现,…...
接口优化常用思路
空间换时间 计算机程序中最大的矛盾是空间和时间的矛盾,那么,从这个角度出发逆向思维来考虑程序的效率问题,我们就有了解决问题的第1招–以空间换时间 合理使用缓存就是一个很好的例子,针对一些频繁使用且不频繁变更的数据&#…...
【SpringCloud】SpringCloud面试题整理
文章目录1、什么是Spring Cloud?2、Spring Cloud和Dubbo的区别3、REST和RPC的区别4、SpringCloud如何实现服务的注册和发现5、什么是服务熔断和服务降级?6、项目中zuul常用的功能7、服务网关的作用8、ribbon和feign区别9、ribbon的负载均衡策略10、简述什…...
一些数据库知识点总结
DB2数据库:从数据库表中第I条记录开始检索J条记录SELECT * FROM (SELECT A.*, ROW_NUMBER() OVER() AS NFROM (SELECT * FROM table_name) AS A)WHERE N > I AND N < J;Oracle数据库:从数据库表中第M条记录开始检索N条记录SELECT * FROM (SELECT R…...
Python unittest 模块
一、Unittest 的几个基本概念 TestCase :要写的具体的测试用例TestSuite: 多个测试用例集合(或测试套件/测试集)TestLoader:用来加载 TestCase 到 TestSuite中的(更通俗一点,就是用来把符合我们…...
Spring - Spring IoC 容器相关面试题总结
文章目录01. Spring IoC 和依赖注入是什么?02. Spring IoC 的优点和缺点分别是什么?03. Spring IoC 有什么作用和功能?04. Spring 依赖注入的方式?05. Spring 构造器注入和 setter 方法注入的区别?06. Spring 依赖注入…...
顺序表来喏!!!
前言:还记得前面的文章:《通讯录的实现》吗?通讯录的完成就借助了顺序表这种数据结构!!!那么今天我们就来介绍我们的顺序表介绍顺序表前,我们来了解一下线性表的概念线性表:线性表&a…...
【H2实践】之 SpringBoot 与 H2 数据交互
一、目标 本文是【H2实践】之认识 H2,【H2实践】之 SpringBoot 整合的后续。前文分别介绍了 H2 及其简单使用,并完成了 H2 与 SpringBoot 的整合。本文将紧接 【H2实践】之 SpringBoot 整合 探索实用 SpringBoot 结合 JPA 通过 web 接口操作 H2 数据库的…...
LeetCode 424. Longest Repeating Character Replacement
LeetCode 424. Longest Repeating Character Replacement https://leetcode.com/problems/longest-repeating-character-replacement/ 题目描述 You are given a string s and an integer k. You can choose any character of the string and change it to any other upperc…...
建立自己的博客(记录-不推荐)
环境安装: w10系统安装 第一步:安装git Git 官网: https://git-scm.com/ 第二步:安装Node.js Node.js官网:https://nodejs.org/zh-cn/ 使用cmd检测: node -v 第三步:安装Hexo Hexo官网:htt…...
hashmap存储方式 hash碰撞及其解决方式
1.Map的存储特点 在Map这个结构中,数据是以键值对(key-value)的形式进行存储的,每一个存储进map的数据都是一一对应的。 创建一个Map结构可以使用new HashMap()以及new TreeMap()两种方式,两者之间的区别是:…...
Amazon GuardDuty 的新增功能 – Amazon EBS 卷的恶意软件检测
亚马逊云科技开发者社区为开发者们提供全球的开发技术资源。这里有技术文档、开发案例、技术专栏、培训视频、活动与竞赛等。帮助中国开发者对接世界最前沿技术,观点,和项目,并将中国优秀开发者或技术推荐给全球云社区。如果你还没有关注/收藏…...
YOLOv7 pytorch
yolov7主干部分结构图:yolov7主干 yolov7数据集处理代码:yolov7数据集处理代码 yolov7训练参数解释:yolov7训练参数【与本文代码有区别】 yolov7训练代码详解:yolov7训练代码详解 目录 训练自己的训练集 训练自己的训练集 此…...
JDK自带JVM分析工具
一、JDK自带工具盘点: jstat:性能分析-查看gc情况; jmap:内存分析-堆信息; jstack:线程分析-栈信息; jinfo:参数查看及配置; jstatd:启动jvm监控服务。它…...
IO多路复用--[select | poll | epoll | Reactor]
因为在简历上写了netty的项目,因此还是将网络底层的那点东西搞清楚。 首先希望明确的是,BIO、NIO、IO多路复用这是不同的东西, 我会在本文中详细讲出来。 本文参考资料: JAVA IO模型 IO多路复用 select poll epoll介绍 从BIO到epo…...
pod的requests、limits解读、LimitRange资源配额、Qos服务质量等级、资源配额管理 Resource Quotas
前言 环境:k8s-v1.22.17 docker-20.10.9 centos-7.9 目录前言什么是可计算资源CPU、Memory计量单位pod资源请求、限额方式pod定义requests、limits查看节点资源情况pod使用request、limits示例LimitRange限制命名空间下的pod的资源配额Qos服务质量等级资源配额管理…...
R语言基础(六):函数
R语言基础(一):注释、变量 R语言基础(二):常用函数 R语言基础(三):运算 R语言基础(四):数据类型 R语言基础(五):流程控制语句 7. 函数 函数是一组完成特定功能的语句。 7.1 内置函数 R语言系统中提供许多内置函数&…...
[C++] 简单序列化
前言 序列化(Serialization) 是将对象的状态信息转换为可以存储或传输的形式的过程。在序列化期间,对象将其当前状态写入到临时或持久性存储区。以后,可以通过从存储区中读取或反序列化对象的状态,重新创建该对象。 使用 序列化 std::array&…...
Autosar Configuration(十三)SomeIP之配置TCP/IP
本系列教程是根据实际项目开发中总结的经验所得,如发现有不对的地方,还请指正。 目录Autosar Configuration(一)Davinci Developer-工具介绍 Autosar Configuration(二)Davinci Developer-SWC配置 Autosar Configuration(三) Security之Crypto配置 Autosar Configurat…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
手游刚开服就被攻击怎么办?如何防御DDoS?
开服初期是手游最脆弱的阶段,极易成为DDoS攻击的目标。一旦遭遇攻击,可能导致服务器瘫痪、玩家流失,甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案,帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
MMaDA: Multimodal Large Diffusion Language Models
CODE : https://github.com/Gen-Verse/MMaDA Abstract 我们介绍了一种新型的多模态扩散基础模型MMaDA,它被设计用于在文本推理、多模态理解和文本到图像生成等不同领域实现卓越的性能。该方法的特点是三个关键创新:(i) MMaDA采用统一的扩散架构…...
华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
CppCon 2015 学习:Time Programming Fundamentals
Civil Time 公历时间 特点: 共 6 个字段: Year(年)Month(月)Day(日)Hour(小时)Minute(分钟)Second(秒) 表示…...
C# winform教程(二)----checkbox
一、作用 提供一个用户选择或者不选的状态,这是一个可以多选的控件。 二、属性 其实功能大差不差,除了特殊的几个外,与button基本相同,所有说几个独有的 checkbox属性 名称内容含义appearance控件外观可以变成按钮形状checkali…...
