代码算法训练营day9 | 28. 实现 strStr() 、459.重复的子字符串

day9:

  • 28. 实现 strStr()
      • KMP的主要应用:
      • 什么是前缀表:
        • 前缀表是如何记录的:
      • 如何计算前缀表:
      • 构造next数组:
        • 1、初始化
        • 2、处理前后缀不相同的情况
        • 3、处理前后缀相同的情况
      • 代码:
  • 459.重复的子字符串(先不做了,)

28. 实现 strStr()

题目链接
状态:KMP不太懂
文档:programmercarl.com

思路:
KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。

KMP的主要应用:

KMP主要应用在字符串匹配上。
KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。

什么是前缀表:

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

举个例子:(在文本串中查找是否存在模式串)
文本串:aa b aa baafa — 模式串:aa b aa f
可以看出,文本串中第六个字符b 和 模式串的第六个字符f,不匹配了。如果暴力匹配,发现不匹配,此时就要从头匹配了。
但如果使用前缀表,就不会从头匹配,而是从上次已经匹配的内容开始匹配。

文本串中的aabaa已经和模式串中的aabaa匹配好了,只有最后一个字符不匹配
那么就要从上次已经匹配好的内容开始匹配,上次和模式串中的 f 前的aa匹配好了的是文本串中的b,所以从模式串中第三个字符b继续开始匹配。

前缀表是如何记录的:

首先要知道前缀表的任务是当前位置匹配失败,找到之前已经匹配上的位置,再重新匹配,此也意味着在某个字符失配时,前缀表会告诉你下一步匹配中,模式串应该跳到哪个位置。

那么什么是前缀表:记录下标 i 之前(包括i)的字符串中,有多大长度的相同前缀后缀。

如何计算前缀表:

前缀表
注意字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串
可以看出模式串与前缀表对应位置的数字表示的就是:下标 i 之前(包括i)的字符串中,有多大长度的相同前缀后缀。

找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。
为什么要前一个字符的前缀表的数值呢,因为要找前面字符串的最长相同的前缀和后缀。所以要看前一位的 前缀表的数值。
前一个字符的前缀表的数值是几, 所以把下标移动到下标为几的位置继续匹配。

next数组既可以就是前缀表,也可以是前缀表统一减一(右移一位,初始位置为-1)。

构造next数组:

我们定义一个函数getNext来构建next数组,函数参数为指向next数组的指针,和一个字符串。 代码如下:

void getNext(int* next, const string& s)

构造next数组其实就是计算模式串s,前缀表的过程。 主要有如下三步:

  1. 初始化
  2. 处理前后缀不相同的情况
  3. 处理前后缀相同的情况
1、初始化

定义两个指针 i 和 j,j 指向前缀末尾位置,i 指向后缀末尾位置。
然后还要对next数组进行初始化赋值,如下:

int j = -1;
next[0] = j;

next[i] 表示 i(包括i)之前最长相等的前后缀长度(其实就是j)

2、处理前后缀不相同的情况

因为j初始化为-1,那么i就从1开始,进行s[i] 与 s[j+1]的比较。
为什么是 i 和 j+1 去比较呢?既然前缀表统一减一了,那么回退的时候也会多回退1,所以就要在 j 上下功夫了,让 j+1,每次比较的时候都比较 j 的后一位。
遍历模式串s的循环下标i 要从 1开始,代码如下:

for (int i = 1; i < s.size(); i++) {

如果 s[i] 与 s[j+1]不相同,也就是遇到 前后缀末尾不相同的情况,就要向前回退。
怎么回退呢?
next[j]就是记录着j(包括j)之前的子串的相同前后缀的长度。
那么 s[i] 与 s[j+1] 不相同,就要找 j+1前一个元素在next数组里的值(就是next[j])。
所以,处理前后缀不相同的情况代码如下:

while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了j = next[j]; // 向前回退
}
3、处理前后缀相同的情况

如果 s[i] 与 s[j + 1] 相同,那么就同时向后移动i 和j,说明找到了相同的前后缀,
所有情况处理结束后,还要将j(前缀的长度)赋给next[i], 因为next[i]要记录相同前后缀的长度。

if (s[i] == s[j + 1]) { // 找到相同的前后缀j++;
}
next[i] = j;

最后整体构建next数组的函数代码如下:

void getNext(int* next, const string& s){int j = -1;next[0] = j;for(int i = 1; i < s.size(); i++) { // 注意i从1开始while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了j = next[j]; // 向前回退}if (s[i] == s[j + 1]) { // 找到相同的前后缀j++;}next[i] = j; // 将j(前缀的长度)赋给next[i]}
}

代码:

class Solution {
public://创建next数组 整体-1void getNext(int* next,string& s){//初始化(后缀i,前缀j,next数组)int j = -1;next[0] = j;//i不能=0,因为还要和j进行比较for(int i=1;i<s.size();i++){//前后缀不相等while(j >= 0 && s[i] != s[j+1]){//j向前一个next的值进行回退j = next[j];}//前后缀相等if(s[i] == s[j+1]){j++; //j向前走一位,同时i也向前走一位}//更新next值next[i] = j; //因为j已经++了,所以已经表示相对应的串的长度了}}int strStr(string haystack, string needle) {if(needle.size() ==0){return 0;}int next[needle.size()];getNext(next,needle); //获取needle的next数组//在文本串s里 找是否出现过模式串tint j = -1; //因为next数组里记录的起始位置为-1//i是从0开始的,因为要从头比for(int i = 0;i<haystack.size();i++){//如果不匹配while(j >= 0 && haystack[i] != needle[j+1]){//j>=0才行,不然next[j]就是无效数据了j = next[j];}//匹配上了if(haystack[i] == needle[j+1]) j++;if(j == needle.size()-1) //比的是j+1 j++后就是j+1的位置return (i-needle.size()+1);}return -1;}
};

459.重复的子字符串(先不做了,)

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

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

相关文章

Mysql 索引、锁与MVCC等相关知识点

文章目录 Mysql锁的类型锁使用MVCC快照读和当前读读视图【Read View】串行化的解决 索引类型存储方式区分逻辑区分实际使用区分索引失效情况 索引建立规范SQL编写规范exlpain字段解析ACID的原理日志引擎慢SQL整合SpringBoot博客记录 Mysql锁的类型 MySQL中有哪些锁&#xff1a…

德人合科技 | 公司办公终端、电脑文件资料 \ 数据透明加密防泄密管理软件系统

天锐绿盾是一款全面的企业级数据安全解决方案&#xff0c;它专注于为企业办公终端、电脑文件资料提供数据透明加密防泄密管理。 首页 德人合科技——www.drhchina.com 这款软件系统的主要功能特点包括&#xff1a; 1. **透明加密技术**&#xff1a; 天锐绿盾采用了透明加密技…

HarmonyOS NEXT应用开发—Grid和List内拖拽交换子组件位置

介绍 本示例分别通过onItemDrop()和onDrop()回调&#xff0c;实现子组件在Grid和List中的子组件位置交换。 效果图预览 使用说明&#xff1a; 拖拽Grid中子组件&#xff0c;到目标Grid子组件位置&#xff0c;进行两者位置互换。拖拽List中子组件&#xff0c;到目标List子组件…

ChromeDriver 122 版本为例 国内下载地址及安装教程

ChromeDriver 国内下载地址 https://chromedriver.com/download 靠谱 千千万万别下载错了 先确认 Chrome 浏览器版本 以 win64 版本为例 那我们下载这一个啊&#xff0c;不要下载错了 下载地址贴在这哈 https://storage.googleapis.com/chrome-for-testing-public/122.0.…

HarmonyOS鸿蒙开发常用4种布局详细说明

介绍一下鸿蒙开发常用4种布局 1、线性布局 2、层叠布局 3、网格布局 4、列表布局 ​1. 线性布局&#xff08;Column/Row&#xff09; 线性布局&#xff08;LinearLayout&#xff09;是开发中最常用的布局&#xff0c;通过线性容器Row&#xff08;行&#xff09;和Column&…

SpringSecurity(SpringBoot2.X版本实现)

资料来源于 SpringSecurity框架教程-Spring SecurityJWT实现项目级前端分离认证授权 侵权删 目录 介绍 快速开始 认证 认证流程 登录校验流程 SpringSecurity完整流程 认证流程详解 代码实现 准备工作 mysql mybatis-plus redis 统一返回类 核心代码 密码加密存…

神策分析 Copilot 成功通过网信办算法备案,数据分析 AI 化全面落地

近日&#xff0c;神策数据严格遵循《互联网信息服务深度合成管理规定》&#xff0c;已完成智能数据问答算法备案。该算法基于大模型技术&#xff0c;专注于为客户提供数据指标查询和数据洞察方面的专业回答。 神策分析 Copilot 运用神策数据智能数据问答算法&#xff0c;聚焦分…

Vue-router3.0版本跳转报错

1.路由创建之后发现控制台push路由跳转报错了 2.解决方法&#xff1a; //在router文件中添加 const originalPush VueRouter.prototype.push VueRouter.prototype.push function push(location) {return originalPush.call(this, location).catch(err > err) }3.解决了

【深度学习模型移植】用torch普通算子组合替代torch.einsum方法

首先不得不佩服大模型的强大之处&#xff0c;在算法移植过程中遇到einsum算子在ONNX中不支持&#xff0c;因此需要使用普通算子替代。参考TensorRT - 使用torch普通算子组合替代torch.einsum爱因斯坦求和约定算子的一般性方法。可以写出简单的替换方法&#xff0c;但是该方法会…

有上百个文件夹需要按顺序编码重命名怎么办?这个方法值得你收藏

在日常生活和工作中&#xff0c;我们经常需要管理大量的文件夹&#xff0c;以便更好地组织和存储文件。为了更方便地查找和识别文件夹&#xff0c;给文件夹按号码命名是一种非常实用的方法。下面&#xff0c;我将详细介绍如何给文件夹按号码命名&#xff0c;并提供一些实用的建…

[Python初阶]2255.统计是给定字符串前缀的字符串数目

目录 2255.统计是给定字符串前缀的字符串数目 ①.题目 ②.问题分析 ③.startswith()方法理解 与 说明 Ⅰ.定义和用法 Ⅱ.语法 ④.问题解决 ⑤总结 2255.统计是给定字符串前缀的字符串数目 ①.题目 ②.问题分析 需求:统计列表words中,是字符串s的前缀的字符串的数目. 解…

【pynput】监控是否打开百度贴吧网页

文章目录 简介Demo 简介 有网友提过一个要求&#xff0c;用 Python 实现一个 电脑打开某网站就自动关机的功能。 想到的思路有两个&#xff1a; 【windows 平台】, 获取活动的窗口标题&#xff0c;如果标题里包含了某些网站名称, 那就使用关机命令 可以定时拉取标题, 也可以使…

Python 导入Excel三维坐标数据 生成三维曲面地形图(体) 5-3、线条平滑曲面且可通过面观察柱体变化(三)

环境和包: 环境 python:python-3.12.0-amd64包: matplotlib 3.8.2 pandas 2.1.4 openpyxl 3.1.2 scipy 1.12.0 代码: import pandas as pd import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D from scipy.interpolate import griddata fro…

【计算机网络_应用层】https协议——加密和窃密的攻防

文章目录 1.https协议的介绍2. 加密和解密2.1 什么是加密2.2 常见的加密方式2.2.1 对称加密2.2.2 非对称加密 2.3 数据摘要&#xff08;数据指纹&#xff09;2.4 数字签名 3. https协议的加密和解密方案一&#xff1a;使用对称加密&#xff08;❌&#xff09;方案二&#xff1a…

嵌入式学习39-程序创建数据库及查找

1.sqlite3_open int sqlite3_open( const char *filename, /* Database filename (UTF-8) */ sqlite3 **ppDb /* OUT: SQLite db handle */ ); 功能: 打开 数据库文件(创建一个数据库连接) 参数: filename: …

react-面试题

一、组件基础 1. React 事件机制 <div onClick{this.handleClick.bind(this)}>点我</div> React并不是将click事件绑定到了div的真实DOM上&#xff0c;而是在document处监听了所有的事件&#xff0c;当事件发生并且冒泡到document处的时候&#xff0c;React将事…

小蓝的漆房——算法思路

题目链接&#xff1a;1.小蓝的漆房 - 蓝桥云课 (lanqiao.cn) 本题只要是通过枚举的方法&#xff0c;算出涂成每一种颜色所需的天数&#xff0c;最后在所有天数中找出最小值&#xff08;由题可知&#xff0c;最多只有60种颜色&#xff0c;所以可以尝试算出每种颜色所需的时间&am…

Linux网络编程: IP协议详解

一、TCP/IP五层模型 物理层&#xff08;Physical Layer&#xff09;&#xff1a;物理层是最底层&#xff0c;负责传输比特流&#xff08;bitstream&#xff09;以及物理介质的传输方式。它定义了如何在物理媒介上传输原始的比特流&#xff0c;例如通过电缆、光纤或无线传输等。…

操作系统内功篇:硬件结构之如何写出让CPU执行更快的代码?

一 前言 因为CPU要操作的数据都在CPU Cache中的话&#xff0c;就不用再从内存中读取数据了&#xff0c;这样就提高了效率&#xff0c;访问的数据在CPU Cache中越多&#xff0c;有个专业名词称为缓存命中率高&#xff0c;所以说&#xff0c;缓存命中率越高&#xff0c;自然执行…

sqllab第三关通关笔记

知识点&#xff1a; 通过回显的信息判断原始语句的组成猜测该语句为 select 1,2,3 from 表名 where id (输入) limit 0,1 首先通过测试判断存在什么类型的sql注入 构造id1/0 发现正常输出&#xff1b;说明是字符型的sql注入 好了&#xff0c;下面就测试有什么限制条件 构造…