【KMP算法最详细讲解】28. 实现 strStr()

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回  -1。

示例 1: 输入: haystack = "hello", needle = "ll" 输出: 2

示例 2: 输入: haystack = "aaaaa", needle = "bba" 输出: -1

说明: 当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。 对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

思路:KMP算法

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

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

前缀表是用来回退的,它记录了当模式串与主串不匹配的时候,模式串应该从哪里和主串重新匹配。

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

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

举个例子:

比如:

模式串:aabaabaaf

字符串:aabaaf

前面匹配了aabaab和aabaaf,发现最后一位不匹配,这个时候,我们知道,前一位也就是aabaa的最后一个a,它对应数字2,就是说最后两个单位长度的后缀,是和它的前缀一样的。所以我们只需要从aabaa的倒数第二个元素对应的原字符串的位置重新开始找。

相当于是,我们发现f这个位置不匹配了,但我们之前f前面的aa,和子串的前两位aa,是一样的,所以子串从它后两位aa对应的长串的位置,重新看aa后面的b与长串aa的后面是不是对应就可以了。

时间复杂度分析:

其中n为文本串长度,m为模式串长度,因为在匹配的过程中,根据前缀表不断调整匹配的位置,可以看出匹配的过程是O(n),之前还要单独生成next数组,时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。

暴力的解法显而易见是O(n × m),所以KMP在字符串匹配中极大地提高了搜索的效率。

生成next数组的过程讲解:

 

class Solution:def getNext(self, next, s):j=-1next[0] = jfor i in range(1, len(s)):while j>=0 and s[i] != s[j+1]:j=next[j]if s[i] == s[j+1]:j += 1next[i] = jdef strStr(self, haystack: str, needle: str) -> int:if not needle:return 0next = [0] * len(needle)self.getNext(next, needle)j = -1for i in range(len(haystack)):while j >= 0 and haystack[i] != needle[j+1]:j = next[j]if haystack[i] == needle[j+1]:j += 1if j == len(needle) - 1:return i-len(needle)+1return -1

这道题还挺难的。以后还需要时常复习和思考。

5月13日 重写:
 

class Solution:def getNext(self, next, s):j=-1next[0]=jfor i in range(1,len(s)):while j>=0 and s[i]!=s[j+1]:j=next[j]if s[i]==s[j+1]:j+=1next[j] = jdef strStr(self, haystack: str, needle: str) -> int:j=-1next=[0]*len(needle)nd = self.getNext(next,needle)for i in range(1,len(nd)):while j>=0 and haystack[i]!=needle[j+1]:j=nd[j]if haystack[i]==needle[j+1]:j+=1

错误点:

在得到next数组的时候,是next[i]=j,而不是next[j]=j

j只是一个暂时的变量,如果不相等,j就回退,如果相等,j就加1,并且让next[i]=j

在寻找needle的时候:

先检查needle是不是为空,如果是,就返回0(在haystack的开头就是空)

不需要让nd=self.getNext(next, needle),因为getNext这个函数传入了next这个list,并且改变了这个list,使得里面有数值,不需要再让另一个list等于它了。

在得到next数组的时候,i从1开始,因为next[0]已经等于j。

但是,在遍历haystack的时候,i从0开始。

判断最后是否在haystack中找到了needle:if j==len(needle)-1

【其实这个点我想到了,但是不知道对不对,所以没有写。看来以后要自信大胆写。】

(因为这个next数组是-1版本的,所以判断条件是j==len(needle)-1)

i指向的是haystack对应的,needle末尾的位置,所以return i-len(needle)+1, 就是needle头出现在haystack的位置了。

如果直到i遍历完,都没有进入这个if,那么就跳出for loop, return -1

注意:

第二个function中,是for i in range(len(haystack)), 而不是for i in range(len(needle))

里面的判断,if statement, 是 haystack[i]和needle[j+1]比较, 而不是haystack[i]和needle[j+1]比较。注意!

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

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

相关文章

C++进阶:哈希(1)

目录 1. 简介unordered_set与unordered_map2. 哈希表(散列)2.1 哈希表的引入2.2 闭散列的除留余数法2.2.1 前置知识补充与描述2.2.2 闭散列哈希表实现 2.3 开散列的哈希桶2.3.1 结构描述2.3.2 开散列哈希桶实现2.3.3 哈希桶的迭代器与key值处理仿函数 3.…

Spring框架概述

目录 1. Spring框架的起源 2. Spring框架的构成 3. Spring的发展历程 4. Spring的开发环境 4.1. Maven安装与配置 (1)Maven的下载与安装 (2)配置Maven的环境变量 (3)本地仓库的配置 (4…

WIFI模块的AT指令联网数据交互--第十天

1.1.蓝牙,ESP-01s,Zigbee, NB-Iot等通信模块都是基于AT指令的设计 初始配置和验证 ESP-01s出厂波特率正常是115200, 注意:AT指令,控制类都要加回车,数据传输时不加回车 1.2.上电后,通过串口输出一串系统…

如何使用dockerfile文件将项目打包成镜像

要根据Dockerfile文件来打包一个Docker镜像,你需要遵循以下步骤。这里假设你已经安装了Docker环境。 1. 准备Dockerfile 确保你的Dockerfile文件已经准备就绪,并且位于你希望构建上下文的目录中。Dockerfile是一个文本文件,包含了用户可以调…

绘制一个单级放大电路原理图过程,保姆级教程

新手在学习pads的使用最好最快的方法就是实际上手去画原理图,画PCB图,在这个过程中,就能够更快速得掌握PADS软件的使用。 本篇就是对于实际画原理图过程的一个记录,手把手教学,如果有纰漏或者有更好的一些技巧&#xf…

thinkphp6使用layui分页组件做分页效果

博主用的是layui2.9.8的版本,但这个版本的分页组件是动态效果的,但我需要的是静态分页,所以我自己封装了一个生成layui的分页代码生成代码。代码如下: 1、先创建文件,路径是extent/layui/LayuiPage.php,加…

R语言:GSEA分析

#安装软件包 > if (!requireNamespace("BiocManager", quietly TRUE)) install.packages("BiocManager") > BiocManager::install("limma") > BiocManager::install("org.Hs.eg.db") > BiocManager::install("…

检测服务器环境,实现快速部署。适用于CRMEB_PRO/多店

运行效果如图: 最近被好多人问,本来运行的好好的,突然swoole就启动不了了。 本工具为爱发电,如果工具正好解决了您的需求。我会很开心 代码如下: """本脚本为爱发电by:网前雨刮器 """…

四川汇昌联信:拼多多网点怎么开?大概需要多少钱?

想要开一家拼多多网点,你肯定很关心需要准备多少资金。下面,我们就来详细解答这个问题,并从多个角度分析开设网点的要点。 一、 开设拼多多网点,首要任务是确定启动资金。根据不同的经营模式和地区差异,成本会有所不同…

基于SpringBoot + Vue的兼职网站管理系统设计与实现+毕业论文+答辩PPT

系统介绍 本系统包含管理员、用户、企业三个角色。 管理员角色:前台首页、个人中心、用户管理、企业管理、兼职信息管理、职位申请管理、留言板管理、系统管理。 用户角色:前台首页、个人中心、职位申请管理。 企业角色:前台首页、个人中心、…

COMSOL粗略估算计算时间

COMSOL粗略估算模型计算时间 针对反复修改调试的有限元模型,需要大致估算有限元模型的计算时间。经查阅,模型求解的自由度数和求解时间密切相关。 测试条件 测试模型为声-固耦合模型,电脑内存32G,CPU-i7-10700K,核显…

【算法】滑动窗口——最小覆盖子串

本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析,有需要借鉴即可。 目录 1.题目2.滑动窗口解法3.总结 1.题目 题目链接:LINK 这个题目是困难难度,感觉是一个中等题目的感觉。 首先我肯定想到的是暴力求解的方法&#xff…

STM32(GPIO)

GPIO简介 GPIO(General Purpose Input Output)通用输入输出口 引脚电平:0V~3.3V,部分引脚可容忍5V 输出模式下可控制端口输出高低电平,用以驱动LED、控制蜂鸣器、模拟通信协议输出时序等 输入模式下可读取端口的高低电…

Java特性之设计模式【享元模式】

一、享元模式 概述 享元模式(Flyweight Pattern)主要用于减少创建对象的数量,以减少内存占用和提高性能。这种类型的设计模式属于结构型模式,它提供了减少对象数量从而改善应用所需的对象结构的方式 享元模式尝试重用现有的同类对…

OS复习笔记ch5-4-2

引言 承接上文我们介绍了信号量机制和应用信号量机制实现的进程同步和互斥,这一节我们将围绕一些经典问题对信号量机制展开更深入地探讨。 读者/写者问题 读者/写者问题与我们之前遇到的问题类型不同,它描述的是: 有读者和写者两组进程&am…

C++初阶学习第七弹——探索STL奥秘(二)——string的模拟实现

标准库中的string:C初阶学习第六弹——string(1)——标准库中的string类-CSDN博客 前言: 在前面我们已经学习了如何使用标准库中的string类,但作为一个合格的程序员,我们不仅要会用,还要知道如…

网络库-libevent介绍

1.简介 libevent是一个事件驱动的网络库,主要用于构建可扩展的网络服务器。它提供了跨平台的API,支持多种事件通知机制,如select、poll、epoll、kqueue等。 主要组件 event: 表示一个具体的事件,包括事件类型、事件回调等。eve…

房屋出租管理系统需求分析及功能介绍

房屋租赁管理系统适用于写字楼、办公楼、厂区、园区、商城、公寓等商办商业不动产的租赁管理及租赁营销;提供资产管理,合同管理,租赁管理, 物业管理,门禁管理等一体化的运营管理平台,提高项目方管理运营效率…

如何查看centos7是否安装nginx

要查看 CentOS 7 系统上是否安装了 Nginx,您可以使用多种方法来检查。以下是一些常见的方法: 通过 RPM 包管理器查询 在 CentOS 系统上,可以使用 RPM 包管理器来查询已安装的软件包。要查看是否安装了 Nginx,您可以在终端中运行以…

【C++】学习笔记——继承_1

文章目录 十一、模板进阶5. 模板的优缺点 十二、继承1. 继承的概念及定义2. 基类和派生类对象赋值转换3. 继承中的作用域4. 派生类的默认成员函数 未完待续 十一、模板进阶 5. 模板的优缺点 优点: 模板复用了代码,节省资源,更快的迭代开发&a…