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

代码随想录第十天(28)

文章目录

  • 28. 找出字符串中第一个匹配项的下标
    • 看答案
    • KMP
      • next数组(前缀表)
      • 最长公共前后缀
      • 如何计算前缀表
      • 前缀表与next数组
      • 时间复杂度分析

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

莫得思路……好久没做题,都已经忘得差不多了

看答案

其实就是自己写一个String的indexOf函数,它的作用是返回某个字符串在另一个字符串中首次出现的位置。

利用的思想是KMP

KMP

例子:
要在文本串:aabaabaafa 中查找是否出现过一个模式串:aabaaf。

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

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

next数组(前缀表)

next数组就是一个前缀表(prefix table)。

前缀表有什么作用呢?

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

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

最长公共前后缀

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

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

正确理解什么是前缀什么是后缀很重要!

所以字符串a的最长相等前后缀为0。 字符串aa的最长相等前后缀为1。 字符串aaa的最长相等前后缀为2。 等等…

匹配的过程在下标5的地方遇到不匹配,模式串是指向f:
在这里插入图片描述
然后应该找到了下标2,指向b,继续匹配:如图:
在这里插入图片描述

以下这句话,对于理解为什么使用前缀表可以告诉我们匹配失败之后跳到哪里重新匹配 非常重要!

下标5之前这部分的字符串(也就是字符串aabaa)的最长相等的前缀 和 后缀字符串是 子字符串aa ,因为找到了最长相等的前缀和后缀,匹配失败的位置是后缀子串的后面,那么我们找到与其相同的前缀的后面重新匹配就可以了。

所以前缀表具有告诉我们当前位置匹配失败,跳到之前已经匹配过的地方的能力。

如何计算前缀表

在这里插入图片描述
长度为前1个字符的子串a,最长相同前后缀的长度为0。
在这里插入图片描述
长度为前2个字符的子串aa,最长相同前后缀的长度为1。

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

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

那么把求得的最长相同前后缀的长度就是对应前缀表的元素,如图:
在这里插入图片描述
找到的不匹配的位置, 那么此时我们要看它的前一个字符的前缀表的数值是多少。

然后移动到,从前一个字符处开始,它对应的前缀表是多少,就向前移多少个位置(不包括前一个元素本身),所以移动到b处

其实这里移动到的位置就是前缀表的元素代表的位置,不用前移多少个元素,比如aabaaf中,f处不匹配,应该移动到它的前一个元素a对应的前缀表元素所指的位置,即字符串下标为2的元素处,即b。

前缀表与next数组

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

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

其实这并不涉及到KMP的原理,而是具体实现,next数组既可以就是前缀表,也可以是前缀表统一减一(右移一位,初始位置为-1)。

时间复杂度分析

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

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

class Solution {public int strStr(String haystack, String needle) {int[] next=new int[needle.length()];next[0]=0;getNext(next,needle);int j=0;for(int i=0;i<haystack.length();i++){//这里的i是从0开始,此时的目的是要将//长的字符串和短的字符串从0号位置开始比较while(j>0&&haystack.charAt(i)!=needle.charAt(j)){j=next[j-1];}if(haystack.charAt(i)==needle.charAt(j)){j++;}if(j==needle.length()){return i-needle.length()+1;}}return -1;}//获得next数组public void getNext(int[] next,String s){int j=0;for(int i=1;i<s.length();i++){//因为要得到前后相等的公共字符串,而next的0位置的元素//一定是0,所以i取1,也就是从next数组的1号元素开始填充while(j>0&&s.charAt(i)!=s.charAt(j)){j=next[j-1];//回退到前个元素的next数组处}if(s.charAt(i)==s.charAt(j)){j++;}next[i]=j;}}
}

相关文章:

代码随想录第十天(28)

文章目录28. 找出字符串中第一个匹配项的下标看答案KMPnext数组&#xff08;前缀表&#xff09;最长公共前后缀如何计算前缀表前缀表与next数组时间复杂度分析28. 找出字符串中第一个匹配项的下标 莫得思路……好久没做题&#xff0c;都已经忘得差不多了 看答案 其实就是自己…...

循环队列来了解一下!!

笔者在之前的一篇文章&#xff0c;详细的介绍了&#xff1a;队列之单向链表与双向链表的模拟实现&#xff1a;https://blog.csdn.net/weixin_64308540/article/details/128742090?spm1001.2014.3001.5502 感兴趣的各位老铁&#xff0c;可以参考一下啦&#xff01;下面进入循环…...

Idea打包springboot项目war包,测试通过

pom.xml文件 <!--包名以及版本号&#xff0c;这个是打包时候使用&#xff0c;版本可写可不写&#xff0c;建议写有利于维护系统--> <artifactId>tsgdemo</artifactId> <version>0.0.1-SNAPSHOT</version> <!--打包形式--> <packaging&…...

python+django高校师生健康信息管理系统pycharm

管理员功能模块 4.1登录页面 管理员登录&#xff0c;通过填写注册时输入的用户名、密码、角色进行登录&#xff0c;如图所示。 4.2系统首页 管理员登录进入师生健康信息管理系统可以查看个人中心、学生管理、教师管理、数据收集管理、问卷分类管理、疫情问卷管理、问卷调查管理…...

CUDA中的流序内存分配

文章目录CUDA中的流序内存分配1. Introduction2. Query for Support3. API Fundamentals (cudaMallocAsync and cudaFreeAsync)4. Memory Pools and the cudaMemPool_t注意&#xff1a;设备的内存池当前将是该设备的本地。因此&#xff0c;在不指定内存池的情况下进行分配将始终…...

开源、低成本的 Xilinx FPGA 下载器(高速30MHz)

目前主流的Xilinx下载器主要有两种&#xff1a;一种是Xilinx官方出品的Xilinx Platfom Cable USB&#xff0c;还有一个就是Xilinx的合作伙伴Digilent开发的JTAG-HS3 Programming Cable。 JTAG-HS系列最大支持30MHz下载速度&#xff0c;基于FTDI的FT2232方案。 JTAG-HS系列对比…...

Maven专题总结

1. 什么是Maven Maven 是一个项目管理工具&#xff0c;它包含了一个项目对象模型 (POM&#xff1a; Project Object Model)&#xff0c;一组标准集合&#xff0c;一个项目生命周期(Project Lifecycle)&#xff0c;一个依赖管理系统(Dependency Management System)&#xff0c;和…...

谷粒商城--SPU和SKU

目录 1.SPU和SKU概念 2.表的关系理解 3.导入前端代码 4.完善后端接口 5.属性分组详情 6.规格参数详情 7. 销售属性详情 8.分组与属性关联 9.发布商品 10.仓库服务 1.SPU和SKU概念 SPU&#xff1a;standard product unit(标准化产品单元)&#xff1a;是商品信息聚合的…...

二叉树OJ题(上)

✅每日一练&#xff1a;100. 相同的树 - 力扣&#xff08;LeetCode&#xff09; 题目的意思是俩棵树的结构不仅要相同&#xff0c;而且每个节点的值还要相同&#xff0c;如果满足上面2个条件&#xff0c;则成立&#xff01; 解题思路&#xff1a; 从三个方面去考虑&#xff1…...

第一章 PDF语法

第一章 PDF语法PDF ObjectsNull ObjectsBoolean ObjectsNumeric ObjectsName ObjectsString ObjectsArray ObjectsDictionary ObjectsName treesNumber treesStream ObjectsDirect versus Indirect ObjectsFile StructureWhite-SpaceThe Four Sections of a PDFHeaderTrailerBo…...

IntelliJ IDEA 创建JavaFX项目运行

IntelliJ IDEA 创建JavaFX项目运行JavaFX官网文档&#xff1a;https://openjfx.io/openjfx-docs/ JavaFX 2008年12月05日诞生&#xff0c;是一个开源的下一代客户端应用程序平台&#xff0c;适用于基于 Java 构建的桌面、移动和嵌入式系统。这是许多个人和公司的协作努力&#…...

IC封装常见形式

参考&#xff1a;https://blog.csdn.net/dhs888888/article/details/127673300?utm_mediumdistribute.pc_relevant.none-task-blog-2defaultbaidujs_baidulandingword~default-0-127673300-blog-115610343.pc_relevant_multi_platform_whitelistv4&spm1001.2101.3001.4242…...

Linux通配符、转义符讲解

目录 通配符 通过通配符定义匹配条件 转义符 将所有的逻辑操作符都转换成字符 通配符 通过通配符定义匹配条件 * 任意字符都可以通配&#xff08;也可以匹配空值&#xff09; &#xff1f; 匹配单个字符 [a-z] 匹配单个的小写英文字母 [A-Z] 匹配单个的大写英文…...

[OpenMMLab]提交pr时所需的git操作

git开发流程 准备工作 作为一个开发者&#xff0c;fork一个仓库之后应该先做什么&#xff1f; 1、下载仓库&#xff0c;创建上游代码库&#xff0c;查看当前的分支情况 git clone https://github.com/<your_name>/<repo_name>.git git remote add upstream git…...

pandas——groupby操作

Pandas——groupby操作 文章目录Pandas——groupby操作一、实验目的二、实验原理三、实验环境四、实验内容五、实验步骤一、实验目的 熟练掌握pandas中的groupby操作 二、实验原理 groupby(byNone, axis0, levelNone, as_indexTrue, sortTrue, group_keysTrue, squeezeFalse&…...

webpack.config.js哪里找?react项目关闭eslint监测

目录 webpack.config.js哪里找&#xff1f; react项目关闭eslint监测 webpack.config.js哪里找&#xff1f; 在React项目中&#xff0c;当我们需要修改一些配置时&#xff0c;发现找不到webpack.config.js&#xff0c;是我们创建的项目有问题吗&#xff0c;还需新创建项目的项…...

OpenCV 图像梯度算子

本文是OpenCV图像视觉入门之路的第12篇文章&#xff0c;本文详细的介绍了图像梯度算子的各种操作&#xff0c;例如&#xff1a;Sobel算子Scharr算子laplacian算子等操作。 OpenCV 图像梯度算子目录 1 Sobel算子 2 Scharr算子 3 laplacian算子 1 Sobel算子 Sobel算子是一种图…...

Linux c编程之Wireshark

Wireshark是一个网络报文分析软件,是网络应用问题分析必不可少的工具软件。网络管理员可以使用wireshark排查网络问题。程序开发人员可以用来分析应用协议、定位分析应用问题。无论是网络应用程序开发人员、测试人员、部署人员、技术支持人员,掌握wireshark的使用对于分析网络…...

极客时间_FlinkSQL 实战

一、批处理以及流处理技术发展 1.Lambda架构三层划分Batch Layer、Speed Layer和Serving Layer。 ①、Batch Layer:主要用于实现对历史数据计算结果的保存,每天计算的结果都保存成为一个Batch View,然后通过对Batch View的计算,实现历史数据的计算。 ②、Speed Layer正是用…...

Pytorch 混合精度训练 (Automatically Mixed Precision, AMP)

Contents混合精度训练 (Mixed Precision Training)单精度浮点数 (FP32) 和半精度浮点数 (FP16)为什么要用 FP16为什么只用 FP16 会有问题解决方案损失缩放 (Loss Scaling)FP32 权重备份黑名单Tensor CoreNVIDIA apex 库代码解读opt-level (o1, o2, o3, o4)apex 的 o1 实现apex …...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

大学生职业发展与就业创业指导教学评价

这里是引用 作为软工2203/2204班的学生&#xff0c;我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要&#xff0c;而您认真负责的教学态度&#xff0c;让课程的每一部分都充满了实用价值。 尤其让我…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

基于开源AI智能名片链动2 + 1模式S2B2C商城小程序的沉浸式体验营销研究

摘要&#xff1a;在消费市场竞争日益激烈的当下&#xff0c;传统体验营销方式存在诸多局限。本文聚焦开源AI智能名片链动2 1模式S2B2C商城小程序&#xff0c;探讨其在沉浸式体验营销中的应用。通过对比传统品鉴、工厂参观等初级体验方式&#xff0c;分析沉浸式体验的优势与价值…...