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

(※)力扣刷题-字符串-实现 strStr()(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() 定义相符。

思路

首先是模式串匹配问题,需要先在hatstack(文本串)中找到needle子串(模式串),然后再去考虑求这个索引。第一个问题就涉及到KMP算法。KMP的经典思想就是:当出现字符串不匹配时,可以记录一部分之前已经匹配的文本内容,利用这些信息避免从头再去做匹配。
以下代码随想录文字详细说明了KMP算法:
https://www.programmercarl.com/0028.%E5%AE%9E%E7%8E%B0strStr.html#%E6%80%9D%E8%B7%AF

解法一-前缀表(减一)

class Solution(object):# 第一步 首先要求next数组def getNext(self, next, s): # s表示模式串# 初始化j = -1next[0] = jfor i in range(1, len(s)): # 注意i从1开始 因为要比较 i 和 j是否相同# 前后缀不相同 while j>=0 and s[i]!=s[j+1]:j = next[j] # j回退# 前后缀相同if s[i]==s[j+1]:j += 1 # i和j都加1next[i] = j# 第二步 求下标索引def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""if not needle:return 0next = [0]*len(needle) # 初始化nextself.getNext(next, needle)j = -1for i in range(len(haystack)):while j >= 0 and haystack[i]!=needle[j+1]: # j+1是因为j初始值为-1j = next[j] # next数组起作用了 找下一个匹配的位置if haystack[i]==needle[j+1]: # 匹配到字符相同j += 1# 判断在文本串里出现了模式串if j == len(needle) - 1:return i - len(needle) + 1 # 返回索引return -1

暴力法

class Solution(object):def strStr(self, haystack, needle):""":type haystack: str:type needle: str:rtype: int"""m, n = len(haystack), len(needle)for i in range(m):if haystack[i:i+n] == needle:return ireturn -1   

使用index(写算法题不推荐)

class Solution:def strStr(self, haystack: str, needle: str) -> int:try:return haystack.index(needle)except ValueError:return -1

使用find(写算法题不推荐)

class Solution:def strStr(self, haystack: str, needle: str) -> int:return haystack.find(needle)

相关文章:

(※)力扣刷题-字符串-实现 strStr()(KMP算法)

28 实现 strStr() 实现 strStr() 函数。 给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。 示例 1: 输入: haystack “hello”, needle “ll” 输出: 2 示例…...

Redis 集群 Redis 事务 Redis 流水线 Redis 发布订阅 Redis Lua脚本操作

Redis 集群 & Redis 事务 & Redis 流水线 & Redis 发布订阅 Redis 集群linux安装redis主从配置查看当前实例主从信息 Redis Sentinelsentinel Redis Cluster Redis 事务Redis 流水线Redis 发布订阅Redis Lua脚本操作 Redis 集群 linux安装redis 下载安装包&#…...

【算法与数据结构】--常见数据结构--栈和队列

一、栈 栈(Stack) 是一种基本的数据结构,具有后进先出(LIFO)的特性,类似于现实生活中的一叠盘子。栈用于存储一组元素,但只允许在栈顶进行插入(入栈)和删除(…...

Linux shell编程学习笔记11:关系运算

Linux Shell 脚本编程和其他编程语言一样,支持算数、关系、布尔、字符串、文件测试等多种运算。前面几节我们研究了 Linux shell编程 中的 字符串运算 和 算术运算,今天我们来研究 Linux shell编程中的的关系运算。 一、关系运算符功能说明 运算符说明…...

JS标准库

学习一门编程语言不仅是掌握其语法。同等重要的是学习其标准库,从而熟练掌握语言本身提供的所有工具。 1 定型数组 js常规数组与C和Java等较低级语言的数组类型还是有很大区别。ES6新增了定型数组,与这些语言的低级数组非常接近。 定型数组严格来说并…...

Android 12.0 hal层添加自定义hal模块功能实现

1. 前言 在12.0的系统rom定制化开发中,在 对hal模块进行开发时,需要通过添加自定义的hal模块来实现某些功能时,就需要添加hal模块的相关功能,接下来就来实现一个案例来供参考 接下来就来具体实现这个功能 2.hal层添加自定义hal模块功能实现的核心类 hardware\interfaces…...

如何理解vue声明式渲染

Vue.js中的声明式渲染是一种用来描述用户界面的方式,它强调“声明”应该如何渲染页面,而不需要关心底层的DOM操作。这与传统的命令式渲染方式,即手动控制DOM元素的创建、更新和销毁,形成了鲜明的对比。 理解Vue的声明式渲染的关键…...

【已解决】Vue全局引入scss 个别页面不生效 / 不自动引入全局样式

项目里配置了全局样式的引入,今天新建了 demo 页面去修改 element 的样式,发现全局的样式没有引入进来。 问题原因 在此页面 没有任何样式导致的 项目在编译的时候,会把 .vue 文件的样式抽离到单独的 css 文件中。 当该页面没有css代码的时…...

MySQL之双主双从读写分离

一个主机 Master1 用于处理所有写请求,它的从机 Slave1 和另一台主机 Master2 还有它的从 机 Slave2 负责所有读请求。当 Master1 主机宕机后, Master2 主机负责写请求, Master1 、 Master2 互为备机。架构图如下 : 准备 我们…...

使用eBPF加速阿里云服务网格ASM

背景 随着云原生应用架构的快速发展,微服务架构已经成为了构建现代应用的主要方式之一。而在微服务架构中,服务间的通信变得至关重要。为了实现弹性和可伸缩性,许多组织开始采用服务网格技术来管理服务之间的通信。 Istio作为目前最受欢迎的…...

大型数据集处理之道:深入了解Hadoop及MapReduce原理

在大数据时代,处理海量数据是一项巨大挑战。而Hadoop作为一个开源的分布式计算框架,以其强大的处理能力和可靠性而备受推崇。本文将介绍Hadoop及MapReduce原理,帮助您全面了解大型数据集处理的核心技术。 Hadoop简介 Hadoop是一个基于Google…...

LCR 095. 最长公共子序列(C语言+动态规划)

1. 题目 给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符&#xff08…...

程序员不写注释:探讨与反思

一、为什么程序员不写注释 当程序员选择不写注释时,通常有一系列常见原因,这些原因可以影响他们的决策和行为。同时,这个决策可能会带来多方面的影响和后果。以下是详细阐述为什么程序员不写注释的常见原因以及这种决策可能导致的影响和后果…...

《论文阅读:Dataset Condensation with Distribution Matching》

点进去这篇文章的开源地址,才发现这篇文章和DC DSA居然是一个作者,数据浓缩写了三篇论文,第一篇梯度匹配,第二篇数据增强后梯度匹配,第三篇匹配数据分布。DC是匹配浓缩数据和原始数据训练一次后的梯度差,DS…...

免费chatGPT工具

发现很多人还是找不到好用的chatGPT工具,这里分享一个邮箱注册即可免费试用。 PromptsZone - 一体化人工智能平台使用 PromptsZone 与 ChatGPT、Claude、AI21 Labs、Google Bard 聊天,并使用 DALL-E、Stable Diffusion 和 Google Imagegen 创建图像&…...

数据分析基础:数据可视化+数据分析报告

数据分析是指通过对大量数据进行收集、整理、处理和分析,以发现其中的模式、趋势和关联,并从中提取有价值的信息和知识。 数据可视化和数据分析报告是数据分析过程中非常重要的两个环节,它们帮助将数据转化为易于理解和传达的形式&#xff0…...

settings.xml的文件配置大全

settings.xml 文件中最常配置的还是这几个标签 localRepository和mirrors settings.xml文件官方文档地址 <settings xmlns"http://maven.apache.org/SETTINGS/1.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"ht…...

极简c++(7)类的继承

为什么要用继承 子类不必复制父类的任何属性&#xff0c;已经继承下来了&#xff1b;易于维护与编写&#xff1b; 类的继承与派生 访问控制规则 一般只使用Public&#xff01; 构造函数的继承与析构函数的继承 构造函数不被继承&#xff01; 在创建子类对象的时候&…...

DOSBox和MASM汇编开发环境搭建

DOSBox和MASM汇编开发环境搭建 1 安装DOSBox2 安装MASM3 编译测试代码4 运行测试代码5 调试测试代码 本文属于《 X86指令基础系列教程》之一&#xff0c;欢迎查看其它文章。 1 安装DOSBox 下载DOSBox和MASM&#xff1a;https://download.csdn.net/download/u011832525/884180…...

047:mapboxGL本地上传shp文件,在map上解析显示图形

第047个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中本地上传shp文件,利用shapefile读取shp数据,并在地图上显示图形。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共117行)加载shapefile.js方式…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词

Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵&#xff0c;其中每行&#xff0c;每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid&#xff0c;其中有多少个 3 3 的 “幻方” 子矩阵&am…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Qwen系列之Qwen3解读:最强开源模型的细节拆解

文章目录 1.1分钟快览2.模型架构2.1.Dense模型2.2.MoE模型 3.预训练阶段3.1.数据3.2.训练3.3.评估 4.后训练阶段S1: 长链思维冷启动S2: 推理强化学习S3: 思考模式融合S4: 通用强化学习 5.全家桶中的小模型训练评估评估数据集评估细节评估效果弱智评估和民间Arena 分析展望 如果…...

比较数据迁移后MySQL数据库和ClickHouse数据仓库中的表

设计一个MySQL数据库和Clickhouse数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...