代码随想录算法训练营第day9|28. 找出字符串中第一个匹配项的下标、459.重复的子字符串

a.28. 找出字符串中第一个匹配项的下标

题目链接

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

示例 1:

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

示例 2:

输入:haystack = "leetcode", needle = "leeto"
输出:-1
解释:"leeto" 没有在 "leetcode" 中出现,所以返回 -1 。

思路:利用kmp算法减少回退步数

        

        KMP主要应用在字符串匹配上。

        KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。所以如何记录已经匹配的文本内容,是KMP的重点,也是next数组肩负的重任。

        next数组就是一个前缀表(prefix table),前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。

        

        文章中字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串

        正确理解什么是前缀什么是后缀很重要!因为前缀表要求的就是相同前后缀的长度。

接下来就要说一说怎么计算前缀表。

如图:

KMP精讲5

长度为前1个字符的子串a,最长相同前后缀的长度为0。(注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。)

KMP精讲6

长度为前2个字符的子串aa,最长相同前后缀的长度为1(a)。

KMP精讲7

长度为前3个字符的子串aab,最长相同前后缀的长度为0。

以此类推: 长度为前4个字符的子串aaba,最长相同前后缀的长度为1(a)。 长度为前5个字符的子串aabaa,最长相同前后缀的长度为2(aa)。 长度为前6个字符的子串aabaaf,最长相同前后缀的长度为0。

那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图: 

KMP精讲8

可以看出模式串与前缀表对应位置的数字表示的就是:下标i之前(包括i)的字符串中,有多大长度的相同前缀后缀。

再来看一下如何利用 前缀表找到 当字符不匹配的时候应该指针应该移动的位置。如动画所示:

KMP精讲2

找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。

为什么要前一个字符的前缀表的数值呢,因为要找前面字符串的最长相同的前缀和后缀。

所以要看前一位的 前缀表的数值。

前一个字符的前缀表的数值是2, 所以把下标移动到下标2的位置继续比配。 可以再反复看一下上面的动画。

最后就在文本串中找到了和模式串匹配的子串了。

#前缀表与next数组

很多KMP算法的实现都是使用next数组来做回退操作,那么next数组与前缀表有什么关系呢?

next数组就可以是前缀表,但是很多实现都是把前缀表统一减一(右移一位,初始位置为-1)之后作为next数组。

class Solution {
public:void getnextarry(int* next,const string& s){//前缀表-1的写法int j=-1;next[0]=j;for(int i=1;i<s.size();i++){while(j>=0&&s[i]!=s[j+1]){j=next[j];//不相等,回退}if(s[i]==s[j+1]){j++;//相等,继续移动}next[i]=j;//记录前后缀}}int strStr(string haystack, string needle) {if(needle.size()>haystack.size())return -1;if(needle.size()==0)return 0;int next[needle.size()];getnextarry(next,needle);//生成前缀表int j=-1;for(int i =0;i<haystack.size();i++){while(j>=0&&haystack[i]!=needle[j+1]){j=next[j];}if(haystack[i]==needle[j+1]){j++;}//j==needle.size()-1说明模式串遍历完成,找到了对应//则此时文本串中匹配的部分起点=i-模式串长度if(j==needle.size()-1)return (i-needle.size()+1);}return -1;}
};

//前缀表不-1的写法
class Solution {
public:void getNext(int* next, const string& s) {int j = 0;next[0] = 0;for(int i = 1; i < s.size(); i++) {while (j > 0 && s[i] != s[j]) {j = next[j - 1];//用前一步的next数组元素回退}if (s[i] == s[j]) {j++;}next[i] = j;}}int strStr(string haystack, string needle) {if (needle.size() == 0) {return 0;}int next[needle.size()];getNext(next, needle);int j = 0;for (int i = 0; i < haystack.size(); i++) {while(j > 0 && haystack[i] != needle[j]) {j = next[j - 1];}if (haystack[i] == needle[j]) {j++;}if (j == needle.size() ) {return (i - needle.size() + 1);}}return -1;}
};

b.459.重复的子字符串

题目链接

给定一个非空的字符串 s ,检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示:

  • 1 <= s.length <= 104
  • s 由小写英文字母组成

思路:

一个字符串s:abcabc,内部由重复的子串组成,那么这个字符串的结构一定是这样的:

图一

也就是由前后相同的子串组成。

那么既然前面有相同的子串,后面有相同的子串,用 s + s,这样组成的字符串中,后面的子串做前串,前面的子串做后串,就一定还能组成一个s,如图:

图二

所以判断字符串s是否由重复子串组成,只要两个s拼接在一起,里面还出现一个s的话,就说明是由重复子串组成。

当然,我们在判断 s + s 拼接的字符串里是否出现一个s的的时候,要刨除 s + s 的首字符和尾字符,这样避免在s+s中搜索出原来的s,我们要搜索的是中间拼接出来的s。

class Solution {
public:bool repeatedSubstringPattern(string s) {string t=s+s;t.erase(t.begin()); t.erase(t.end()-1);if(t.find(s)!=std::string::npos)return true;return false;}
};

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

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

相关文章

关于JVM的小总结(待补充)

JVM组成及他们之间的关系 装载类子系统字节码执行引擎运行时数据区 装载类子系统 类加载器字节码调节器类加载运行时数据区 字节码执行引擎 运行时数据区 线程私有 虚拟机栈本地方法栈程序计数器 线程共享 堆方法区&#xff08;元空间&#xff09;

Vue3 中的代理原理详解

Vue3 中的代理原理详解 Vue3 中引入了代理&#xff08;Proxy&#xff09;机制&#xff0c;取代了 Vue2 中的 Object.defineProperty() 机制&#xff0c;用于实现数据响应式。代理机制是 ES6 中新增的特性&#xff0c;它可以用来自定义对象中的操作&#xff0c;比如属性查找、赋…

rabbitmq总结

一、初次感知 https://www.cnblogs.com/zqyx/p/13170881.html 这篇文章非常好&#xff0c;讲了一些持久化的原理。 1. 第一次使用rabbitmq发信息 // 创建连接工厂ConnectionFactory connectionFactorynew ConnectionFactory();connectionFactory.setHost("192.168.88.1…

php使用ElasticSearch

ElasticSearch简介 Elasticsearch 是一个分布式的、开源的搜索分析引擎&#xff0c;支持各种数据类型&#xff0c;包括文本、数字、地理、结构化、非结构化。 Lucene与ElasticSearch Apache Lucene是一款高性能的、可扩展的信息检索&#xff08;IR&#xff09;工具库&#xf…

Qt添加VTK并绘制图形

文章目录 准备环境使用VS创建Qt Widget项目配置VTK依赖调试C/C链接器 添加vtk窗口测试代码 参考链接&#xff1a; VS2017配置QT环境(详细版)_vs2017 qt-CSDN博客 QT5VTK9.1最新配置方法_qt vtk-CSDN博客 VTK笔记-Qt5.12.11编译VTK9.0.3-QVTKOpenGLNativeWidget-CSDN博客 准…

Java二级--操作题详解(1)

目录 1.第一套&#xff1a; 1.1 基本操作&#xff1a; 1.2 题解分析&#xff1a; 2.1 简单应用&#xff1a; 2.2 解题分析&#xff1a; 3.1 综合应用&#xff1a; 3.2解题分析&#xff1a; 1.第一套&#xff1a; 1.1 基本操作&#xff1a; 在考生文件夹中存有文件名为J…

Leetcode HOT150

55. 跳跃游戏 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1 …

C++ · 代码笔记3 · 引用

目录 前言011引用初探_引用与普通变量012引用初探_引用作为函数参数013引用初探_引用作为函数返回值014引用初探_引用返回局部函数造成的错误015引用初探_多级引用020引用与指针递增的区别030const与引用040使用const限定的函数形参引用 前言 本笔记所涉及到的编程环境与 《C …

怎么对接迅雷网盘拉新项目?迅雷网盘怎么做才有效果?

自网盘拉新项目上线以来&#xff0c;网盘市场日益繁荣&#xff0c;各大厂商纷纷进军这一领域。头条网盘、悟空网盘、UC网盘、迅雷网盘等都成为了各个推广达人喜欢的推广项目。其中&#xff0c;迅雷网盘凭借其稳定的服务、强大的功能和广泛的用户基础&#xff0c;成为了市场中的…

西门子S120故障报警F30003的解决办法总结

西门子S120故障报警F30003的解决办法总结 如下图所示&#xff0c;压机在回程时突然出现报警&#xff0c;故障代码为&#xff1a;30003&#xff0c; 如下图所示&#xff0c;查找手册可以看到F30003的报警分析为&#xff1a;直流母线欠压 如下图所示&#xff0c;本来想测量输入端…

三八妇女节智慧花店/自动售花机远程视频智能监控解决方案

一、项目背景 国家统计局发布的2023年中国经济年报显示&#xff0c;全年社会消费品零售总额471495亿元&#xff0c;比上年增长7.2%。我国无人零售整体发展迅速&#xff0c;2014年市场规模约为17亿元。无人零售自助终端设备市场规模超过500亿元&#xff0c;年均复合增长率超50%。…

如何阅读“计算机界三大神书”之一 ——《计算机程序的构造和解释》SICP

&#x1f468;‍&#x1f393;博主简介 &#x1f3c5;云计算领域优质创作者   &#x1f3c5;华为云开发者社区专家博主   &#x1f3c5;阿里云开发者社区专家博主 &#x1f48a;交流社区&#xff1a;运维交流社区 欢迎大家的加入&#xff01; &#x1f40b; 希望大家多多支…

总结Redis的原理

一、为什么要使用Redis 缓解数据库访问压力mysql读请求进行磁盘I/O速度慢&#xff0c;给数据库加Redis缓存&#xff08;参考CPU缓存&#xff09;&#xff0c;将数据缓存在内存中&#xff0c;省略了I/O操作 二、Redis数据管理 2.1 redis数据的删除 定时删除惰性删除内存淘汰…

NHANES数据(复杂调查数据)亚组交互函数1.7(P for interaction)发布-纠正了目前的一个问题

大家好&#xff0c;有粉丝私信我说NHANES数据(复杂调查数据)亚组交互函数1.版本交互函数有点问题&#xff0c;我查看了一下&#xff0c;有个代码调用失效了。就是下面这个&#xff0c;本来我是这样调用数据的 ids<-match.call()$ids应该是由于R版本或者survy包升级后导致这…

基于sprinbgoot的火锅店管理系统(程序+数据库+文档)

** &#x1f345;点赞收藏关注 → 私信领取本源代码、数据库&#x1f345; 本人在Java毕业设计领域有多年的经验&#xff0c;陆续会更新更多优质的Java实战项目&#xff0c;希望你能有所收获&#xff0c;少走一些弯路。&#x1f345;关注我不迷路&#x1f345;** 一、研究背景…

从新能源汽车行业自动驾驶技术去看AI的发展未来趋势

自动驾驶汽车关键技术主要包括环境感知、精准定位、决策与规划、控制与执行、高精地图与车联网V2X以及自动驾驶汽车测试与验证技术等。 &#x1f413; 自动驾驶技术 这是AI在汽车行业中应用最广泛的领域之一。自动驾驶技术利用AI算法和传感器来感知环境、识别障碍物&#xff0c…

mysql的语法总结2

命令&#xff1a; mysql -u 用户名 -p mysql登录 命令&#xff1a;create database u1 创建数据库u1 查询数据库 使用数据库u1 创建表department 查询表department ALTER TABLE 表名 操作类型&#xff1b; 操作类型可以有以下的操作&#xff1a; 添加列&#x…

[Redis]——Spring整合Redis(SpringDataRedis)

⭐准备工作&#xff1a; 确保Redis服务已启动idea开发环境 ⭐Redis整合步骤&#xff1a; 1.pom文件引入依赖 2.yml文件配置连接信息 3.修改Redis序列化方式 4.注入RedisTemplate 使用 小知识&#xff1a; Spring整合的Redis可以将Object对象自动序列化成字符串&#xff0…

【C++干货基地】面向对象核心概念 | 访问限定符 | 类域 | 实例化 | 类对象模型

&#x1f3ac; 鸽芷咕&#xff1a;个人主页 &#x1f525; 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想&#xff0c;就是为了理想的生活! 引入 哈喽各位铁汁们好啊&#xff0c;我是博主鸽芷咕《C干货基地》是由我的襄阳家乡零食基地有感而发&#xff0c;不知道各位的…

【ETCD】简介安装常用操作---图文并茂详细讲解

目录 一 简介 1.1 etcd是什么 1.2. 特点 1.3. 使用场景 1.4 关键字 1.5 工作原理 二 安装 2.1 etcd安装前介绍 2.2 安装 2.3 启动 2.4 创建一个etcd服务 三 常用操作 一 简介 1.1 etcd是什么 etcd是CoreOS团队于2013年6月发起的开源项目&#xff0c;它的目标是构建…