【刷题笔记】匹配字符串||KMP||动图解析||符合思维方式

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

1 题目描述

https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/

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

2 思路

其实说白了,这道题的意义就是为了让我们理解KMP算法。

网上很多讲解一上来就解释next数组怎么构建的,如何计算前缀等。但是我认为最重要的还是先明白KMP算法在做什么。

如下图,图中有上下两个字符串,上串为haystack,下串为needle

在这里插入图片描述

在这里插入图片描述

右移:

在这里插入图片描述

提示:为了让大家清晰地看懂我要说什么,这里我先规定几个词的含义:
前缀和后缀:指的是在needle的子串(我们设置为part_needle=needle[:n])中,一个从头开始的字符子串a和一个与其相同的但是末尾是part_needle的末尾的字符子串b
即:
a=[part_needle[0], ..., part_needle[1], ..., part_needle[prefix_len-1]
其实本质上也是a=[needle[0], ..., needle[1], ..., needle[prefix_len-1]
b=[part_needle[-prefix_len]], part_needle[-(prefix_len - 1), ..., part_needle[-1]

💡:a==b

prefix_len就是前缀和后缀的长度,而且是子串part_needle满足条件的最大值
如果嫌麻烦可以看看上面的第一张图就一目了然了。

我们的目标是,当遇到不匹配的时候,能够让needle尽可能地右移动,而不是每次只移动一个位置。为什么?

我们先看一个动图:

在这里插入图片描述

我们这里将一开始的图进行了细化,可以看到,needlehaystack已经有8个字符完成了匹配(黄色和绿色字符),在第九个字符的时候,haystack是橘色,needle是红色,不匹配。我们可以看到,正常情况下的第一个想法是将needle后移一位,重新开始匹配。

此时,红色字符之前的八个字符已经构成了一个needle的子串part_needle=needle[:8]。假设我们已经找到了这个子串中最长的前缀和后缀(黄色部分),那么在前六步移动的时候,请仔细看紫色框里的字符串,这些字符串是不可能相等的,因为我们知道在前八个字符中,只有前两个字符构成的串和倒数后两个字符构成的串相等,那么我们可以直接跳过前六步,到达第七步。

注意,上面这段话的描述是KMP思想的关键,只有看懂了我上面说的什么,你才能知道KMP到底在干什么。请结合动图再看一遍,我希望我能够把我领悟到的东西让你也感受到。

那么我们现在的目标就是找出,needle的每个子串(注意都是从0号索引开始的子串)的前缀和后缀。比如needleleetcode,那么子串分别为:

l 第0个子串
le 第1个子串
lee 第2个子串
leet 第3个子串
leetc
leetco
leetcod

2.1 找到前缀长度

知道了子串是什么之后,我们要想找前缀和后缀,本质上就是在找前缀和后缀的长度。

现在让我们把目光只盯向needle
在这里插入图片描述

当我们到达一个未知子串的时候,该怎么找到未知子串中的前缀和后缀呢?

但是此时我已经有了前面所有子串的前缀和后缀,如果当前的字符(红色)和前缀后面的字符相等,如下图所示,
在这里插入图片描述

那么便可以确定当前的前缀和后缀了。

可是如果不等呢?是不是就说明当前未知子串没有前后缀?非也。我们换一种表示方式,不用圆圈表示字符了,只用颜色表示字符。

在这里插入图片描述

我们发现,虽然紫色和红色不相等,但是在黄色区域中,放大来看其实内有乾坤(黄色区域其实只是表示一个字符串),黄色区域也有前缀和后缀(蓝色部分),第一个黄色区域和第二个黄色区域具有量子纠缠的神奇性质,因为它们相等,所以第一个黄色区域的特征,第二个黄色区域也全都有。黄色区域的前缀蓝色,下一个字符是红色,正好跟我们的未知子串的最后一个字符一样是红色。

在这里插入图片描述

(不要考虑宽度,宽度在本小节的语境下没有意义)

这样我们知道了,如果我们的未知子串的最后一个字符和已知的上一个子串的前缀的后一个字符不相等,那么我们可以让未知字符的子串继续跟前缀的前缀的后一个字符去比较,一直迭代下去。直到找到相等字符或者某个前缀内部已经没有前缀了。

Wait,上面的叙述,好像就是动态规划吧。当前字符串的前后缀长度和上一个字符串有关。

我们设这个记录长度的数组为:

int[] prefix_len_dps = new int[needle.length()];
prefix_len_dps[0] = 0;

比如prefix_len_dps[2]就是记录的前三个字符构成的字符串的前后缀长度。

for (int i = 1; i < needle.length(); i++) {
    int prefix_len = prefix_len_dps[i - 1]; // 前一个子串的前后缀长度
    while (needle.charAt(prefix_len) != needle.charAt(i) && prefix_len > 0)
    // 首先我们要理解一点,长度可以用作下标,
    // needle.charAt(prefix_len)其实就是第i-1个子串前缀的后面一个字符
    // 如果needle.charAt(prefix_len) != needle.charAt(i),说明我们需要找前缀的前缀
    // 我们说过,prefix_len是第i-1个子串前缀的后面一个字符的位置,那么
    // prefix_len-1就是第i-1个子串的末尾的位置,
    // prefix_len_dps[prefix_len - 1]表示的就是第i-1个子串的前缀长度,即前缀的前缀的长度
    // 如果prefix_len==0,这说明第i-1个子串没有前缀,那么我们直接跳出循环,让第i个子串
    // 的第一个字符跟最后一个字符相比较
        prefix_len = prefix_len_dps[prefix_len - 1];
    if (needle.charAt(prefix_len) == needle.charAt(i)) prefix_len++;
    prefix_len_dps[i] = prefix_len;
}

2.2 找到匹配下标

int j = 0;
for (int i = 0; i < haystack.length(); i++) {
    while (haystack.charAt(i) != needle.charAt(j) && j > 0) {
        j = prefix_len_dps[j - 1] // 循环,找到第一个可以匹配的j
        // 其实这里的逻辑跟前面是一样的,我们期待接下来的i和j位置上的
        // 字符可以相等,如果不相等,就继续找其前缀的后一个位置,还不等,那就找前缀的前缀。。。
        // 一直到j==0,没有前缀了,跳出,然后直接比较
        // needle的第一个字符和haystack在i位置上的字符
    }
    if (haystack.charAt(i) == needle.charAt(j)) j++;
    if (j == needle.length()) return i - needle.length() + 1;
}

3 代码

class Solution {
    public int strStr(String haystack, String needle) {
        int[] prefix_len_dps = new int[needle.length()];
        prefix_len_dps[0] = 0;
        for (int i = 1; i < needle.length(); i++) {
            int prefix_len = prefix_len_dps[i - 1];
            while (needle.charAt(prefix_len) != needle.charAt(i) && prefix_len > 0)
                prefix_len = prefix_len_dps[prefix_len - 1];
            if (needle.charAt(prefix_len) == needle.charAt(i)) prefix_len++;
            prefix_len_dps[i] = prefix_len;
        }

        int j = 0;
        for (int i = 0; i < haystack.length(); i++) {
            while (haystack.charAt(i) != needle.charAt(j) && j > 0)
                j = prefix_len_dps[j - 1];
            if (haystack.charAt(i) == needle.charAt(j)) j++;
            if (j == needle.length()) {
                return i - needle.length() + 1;
            }
        }
        return -1;
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

IP-Adapter:文本兼容图像提示适配器,用于文本到图像扩散模型

IP-Adapter这是一种有效且轻量级的适配器&#xff0c;用于实现预训练文本到图像扩散模型的图像提示功能。只有 22M 参数的 IP 适配器可以实现与微调图像提示模型相当甚至更好的性能。IP-Adapter 不仅可以推广到从同一基本模型微调的其他自定义模型&#xff0c;还可以推广到使用…

OpenVINO异步Stable Diffusion推理优化方案

文章目录 Stable Diffusion 推理优化背景技术讲解&#xff1a;异步优化方案思路&#xff1a;异步推理优化原理OpenVINO异步推理Python API同步和异步实现方式对比 oneflow分布式调度优化优势&#xff1a;实现思路 总结&#xff1a; Stable Diffusion 推理优化 背景 2022年&am…

Selenium 连接到现有的 Firefox 示例

当前环境&#xff1a; python 3.7 selenium 3.14.1 urllib3 1.26.8 Frefox 115.1.0esr(32位) geckodriver.exe 0.33.0 1 下载 Firefox 浏览器&#xff0c;根据自己的需要选择。 下载 Firefox 浏览器&#xff0c;这里有简体中文及其他 90 多种语言版本…

招标采购软件如何让采购变得更轻松?

企业总是希望让采购流程更简单&#xff0c;选择更好的供应商&#xff0c;花更少的钱。采购软件的普及使原材料和服务的采购变得更容易&#xff0c;向供应商&#xff08;甚至是全球供应商&#xff09;索取信息的流程已大大简化。包括招标采购软件在内的采购技术已成为企业运营不…

Elasticsearch(ES)概述

文章目录 一.什么是Elasticsearch?1.正向索引和倒排索引2.Mysql和ES的概念对比3.安装elasticsearch、kibana 二.IK分词器三.索引库操作四.文档操作五.RestClient操作索引库1.初始化RestClient2.创建索引库3.删除索引库4.判断索引库是否存在 六.RestClient操作文档1.新增文档2.…

【开发实践】使用POI实现导出带有复杂表头的的excel文件

一、需求分析 公司业务部门需要&#xff0c;根据一些数据&#xff0c;加上表头&#xff0c;导出需要的excel表格。效果如下&#xff1a; 二、代码实现 【依赖准备】 <!-- POI --><dependency><groupId>org.apache.poi</groupId><artifactId>po…

CloudCompare简单开发

一、概述 CloudCompare如何进行二次开发&#xff1f;_cloudcompare 二次开发-CSDN博客 开发一个功能&#xff0c;在原始CC的基础上添加一个拓展功能&#xff0c;如下&#xff1a; 二、功能开发 1、修改MainWindow.UI 重点是&#xff1a;要编译&#xff0c;不然在mainwindow.…

P8A110-A120经典赛题

Web应用程序SQL Inject安全攻防 任务环境说明&#xff1a; 服务器场景&#xff1a;WebServ2003&#xff08;用户名&#xff1a;administrator&#xff1b;密码&#xff1a;空&#xff09;服务器场景操作系统&#xff1a;Microsoft Windows2003 Server 服务器场景安装服务/工…

yolov5检测(前向)输入视频输出(不在图上画标签形式的原)图片的方法,及设置每隔几帧保存的方式(不每帧保存减少重复)

这些天我忽然有个需求&#xff0c;要更新迭代一个场景的检测模型&#xff0c;甲方爸爸提供的新数据集是监控视频形式的(因为拍视频确实更加的方便)&#xff0c;而我训练模型确实要标注好的图片形式。 根据这些条件的话&#xff0c;思路应该是要这样的&#xff1a;首先使用现有的…

【Android知识笔记】性能优化专题(四)

App 线程优化 线程调度原理 任意时刻,只有一个线程占用CPU,处于运行状态多线程并发:轮流获取CPU使用权JVM负责线程调度:按照特定机制分配CPU使用权线程调度模型 分时调度模型:轮流获取、均分CPU时间抢占式调度模型:优先级高的获取,JVM采用Android线程调度 nice值:Proc…

解密Python内置类属性__getitem__的神奇魔力:深入探索索引访问的奥秘

概要 在Python编程语言中&#xff0c;__getitem__是一种内置的类属性&#xff0c;它允许我们以索引的方式访问对象的元素。这个魔法方法在Python中被广泛使用&#xff0c;它不仅让我们能够使用索引来访问对象的元素&#xff0c;还能让我们自定义对象的索引访问方式&#xff0c…

STM32 ADC转换器、串口输出

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、ADC是什么&#xff1f;二、STM32的ADC2.1 认识STM32 ADC2.2转换方式2.3 为什么要校准&#xff1f;2.4 采样时间计算2.5 触发方式2.6 多通道采集解决方案2.7…

Hutool是一个小而全的Java工具类库

Hutool是一个小而全的Java工具类库&#xff0c;它包含了众多实用的静态方法&#xff0c;可以提高Java开发效率。以下是Hutool的安装和使用教程&#xff1a; 安装 Hutool可以通过Maven或Gradle进行安装。 ① Maven安装&#xff1a; 在您的Maven项目的pom.xml文件中添加以下依赖…

linux 安装 mvn

mvn 下载地址&#xff1a;https://maven.apache.org/download.cgi 选择一个合适的版本 cd /opt && curl -o apache-maven-3.8.6-bin.tar.gz https://dlcdn.apache.org/maven/maven-3/3.8.6/binaries/apache-maven-3.8.6-bin.tar.gz tar -xzf apache-maven-3.8.6-bin.…

Windows平台下的oracle 11G-11.2.0.4补丁升级操作指南

序号 文件名称 文件说明 1 p6880880_112000_MSWIN-x86-64_OPatch 11.2.0.3.33 for DB 11.2.0.0.0 (Feb 2022) 用于升级 OPatch 2 DB_PSU_11.2.0.4.220118 (Jan 2022)_p33488457_112040_MSWIN-x86-64 主要补丁文件 注意&#xff1a;请用管理员权限运行文件内命令&#…

【JavaSE】:接口(一)

接口 一.什么是接口二.语法规则三.接口的使用四.实现多个接口五.接口的继承 final关键字 inal修饰的变量&#xff0c;这个变量是不可修改的。final修饰后的方法&#xff0c;禁止子类继承的时候重写方法。final修饰后的类&#xff0c;是禁止被继承的。 super关键字 如果父类(超类…

Programming Abstractions in C阅读笔记:p197-p201

《Programming Abstractions in C》学习第64天&#xff0c;p196-p201总结。 一、技术总结 很难&#xff0c;唯有继续往下看才能让其变容易。 二、英语总结 1.psychologically是什么意思&#xff1f; 答&#xff1a; (1))psychology > psychological > psychologica…

pg truncate

命令选项 TRUNCATE [ TABLE ] [ ONLY ] name [ * ] [, ... ][ RESTART IDENTITY | CONTINUE IDENTITY ] [ CASCADE | RESTRICT ]1.ONLY:只truncate指定的表。当表有继承子表或有子分区时&#xff0c;默认会一起truncate;only可只truncate继承父表。分区父表不能指定only --不…

负索引和负方向

在python里有序集合的index位置信息可正可负&#xff0c;方向可以从左向右或从右向左。以“python”字符串通过list函数转化生成的列表为例&#xff0c;其正负位置信息index值如下所示&#xff1a; 0 1 2 3 4 5 p y t h o n -6 -5 -4 -3 -2 -1 故&#xff0c;切片的start、end、…

Vue框架学习笔记——绑定class样式和绑定style样式

文章目录 前文提要class样式的三种绑定方法&#xff08;图片来自参考链接&#xff09;style样式&#xff08;内联形式&#xff09;总结 前文提要 本人仅做个人学习记录&#xff0c;如有错误&#xff0c;请多包涵 主要学习链接&#xff1a;尚硅谷Vue2.0Vue3.0全套教程丨vuejs从…