力扣 LeetCode 28. 找出字符串中第一个匹配项的下标(Day4:字符串)

解题思路:

KMP算法

需要先求得最长相等前后缀,并记录在next数组中,也就是前缀表,前缀表是用来回退的,它记录了模式串与主串(文本串)不匹配的时候,模式串应该从哪里开始重新匹配。

next[ j - 1 ] 记录了 j 要回退的位置(注意要限制 j > 0 )

最长相等前后缀的例子如下:

a             0

aa           1

aab         0

aaba       1

aabaa     2

aabaaf    0

KMP算法的应用,例如:

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

第一次匹配aabaaf时,aabaa成功,到f时失败

根据回退

aabaa的最长相等前后缀为2

即 j 回到下标为2的位置,也就是b

第二次匹配时,即为aabaabaaf 中的baaf开始匹配

(因为匹配到的串文本串和模式串是前后对称的,即aabaa和aabaa,aabaa的尾和aabaa的头中的aa可以续接上,所以不用再从aa开始了,aa已经匹配到了,直接从b开始)

匹配成功

class Solution {public int strStr(String haystack, String needle) {int[] next = new int[needle.length()];getNext(next, needle);int j = 0;for (int i = 0; i < haystack.length(); i++) {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;}public void getNext(int[] next, String needle) {int j = 0;next[0] = 0;for (int i = 1; i < needle.length(); i++) {while (j > 0 && needle.charAt(i) != needle.charAt(j)) j = next[j - 1];if (needle.charAt(i) == needle.charAt(j)) j++;next[i] = j;}}
}

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

计算机网络 (1)互联网的组成

一、互联网的边缘部分 互联网的边缘部分由所有连接在互联网上的主机组成&#xff0c;这些主机又称为端系统&#xff08;end system&#xff09;。端系统可以是各种类型的计算机设备&#xff0c;如个人电脑、智能手机、网络摄像头等&#xff0c;也可以是大型计算机或服务器。端系…

智慧军营安防方案

1. 引言 智慧安防方案集成高清视频监控、智能分析与大数据管理&#xff0c;打造全方位安全防护体系。通过先进技术&#xff0c;提升预警与应急响应能力&#xff0c;确保安全无死角。 2. 视频监控技术 采用高清摄像设备与智能识别算法&#xff0c;实现全景监控与细节跟踪&#…

ABAP开发学习——ST05 ABAP SQL跟踪工具

操作步骤 第一步使用ST05之前&#xff0c;将要查的程序停留想要看的操作的前一步&#xff0c;这里想看到取数操作&#xff0c;所以停留在选择界面 第二步进入ST05 选择SQL Trace 然后激活 第三步去执行程序 第四步ST05取消激活 第五步查看操作 选完时间直接执行

AtCoder ABC378 A-D题解

比赛链接:ABC378 比较简单的一次 ABC。 Problem A: Code #include <bits/stdc.h> using namespace std; int main(){cin>>A[1]>>A[2]>>A[3]>>A[4];sort(A1,A5);if(A[1]A[2] && A[3]A[4])cout<<2<<endl;else{if(A[1]A[2]…

Windows上安装专业版IDEA2024并激活

1、IDEA官方下载 搜索IDEA官网点击进入&#xff0c;点击Download&#xff08;目前这个激活脚本只能激活2024.1.7&#xff0c;2024.2.x的版本都不能激活&#xff0c;2024.1.7版本已上传资源&#xff09;&#xff0c;如图&#xff1a; 2、开始安装 1&#xff09;、双击下载的.…

表达式求值问题(中缀转后缀,对后缀求值)详解

目录 实验题目 理解中缀和后缀表达式 问题分析 1转化为中缀表达式 2计算后缀表达式 完整代码 运行结果 实验题目 实验题目&#xff1a;表达式求值问题。这里限定的表达式求值问题是&#xff1a; 用户输入一个包含“”、“-”、“*”、“/”、正整数和圆括号的合法数学表…

AD22怎么按照板子形状铺铜

如何按照板子形状来铺铜&#xff1f; 选择铺铜管理器 选择板外形 我这里图里VCC没画就选择VCC&#xff0c; 你选什么层&#xff0c;就勾什么层 死铜移除勾选 效果如下&#xff1a;

【视觉SLAM】2-三维空间刚体运动的数学表示

读书笔记&#xff1a;学习空间变换的三种数学表达形式。 文章目录 1. 旋转矩阵1.1 向量运算1.2 坐标系空间变换1.3 变换矩阵与齐次坐标 2. 旋转向量和欧拉角2.1 旋转向量2.2 欧拉角 3. 四元数 1. 旋转矩阵 1.1 向量运算 对于三维空间中的两个向量 a , b ∈ R 3 a,b \in \R^3 …

研发费用资本化的意义

1.更真实地反映企业价值&#xff1a;研发费用是企业为创造未来经济利益而进行的投资&#xff0c;通过将其资本化并作为无形资产计入资产负债表&#xff0c;可以更真实地反映企业的资产总额和长期投资价值。这有助于投资者、债权人和其他利益相关者更准确地评估企业的财务状况、…

Ubuntu24.04安装Anaconda3+Pycharm

一、引言 重装系统已经过去一段时间了&#xff0c;现在安装一下 Anaconda 和 Pycharm。 参考连接&#xff1a; Ubuntu中安装Anaconda3和Pycharm 及其环境搭建Ubuntu18.04安装Pycharm教程ubuntu系统安装Anaconda及Pycharm在移动硬盘上搭建Ubuntu24.04深度学习环境&#xff08;…

稀疏矩阵(Sparse Matrix)及其存储格式详解

稀疏矩阵&#xff08;Sparse Matrix&#xff09;是线性代数和计算机科学中的一个重要概念&#xff0c;广泛应用于科学计算、工程模拟、图像处理、机器学习等多个领域。与稠密矩阵&#xff08;Dense Matrix&#xff09;相比&#xff0c;稀疏矩阵大部分元素为零&#xff0c;仅有少…

操作系统:页表中的页表项

操作系统&#xff1a;页表中的页表项 页表是操作系统用于跟踪进程使用的虚拟地址与系统内存中相应物理地址之间映射的数据结构。 页表项&#xff08;Page Table Entry&#xff0c;PTE&#xff09;是页表中的一个条目&#xff0c;用于存储有关特定内存页的信息。每个页表项包含…

Docker部署Kafka SASL_SSL认证,并集成到Spring Boot

1&#xff0c;创建证书和密钥 需要openssl环境&#xff0c;如果是Window下&#xff0c;下载openssl Win32/Win64 OpenSSL Installer for Windows - Shining Light Productions 还需要keytool环境&#xff0c;此环境是在jdk环境下 本案例所使用的账号密码均为&#xff1a; ka…

文章解读与仿真程序复现思路——电力系统自动化EI\CSCD\北大核心《基于改进容积卡尔曼滤波的含光伏配电网动态状态估计》

本专栏栏目提供文章与程序复现思路&#xff0c;具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…

jenkins使用cli发行uni-app到h5

官网文档HBuilderX 文档 首先确定是否存在环境变量 正常情况cmd中执行cli 如果提示 cli 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。请先配置环境变量 Freestyle Project项目在Build Steps中增加Execute Windows batch command命令如下 d: cd D:\devsof…

FMEA 在新兴技术领域(如量子计算、人工智能芯片等)的应用挑战与机遇

【大家好&#xff0c;我是唐Sun&#xff0c;唐Sun的唐&#xff0c;唐Sun的Sun。】 摘要&#xff1a; 本文深入探讨了 FMEA&#xff08;失效模式及后果分析&#xff09;在如量子计算、人工智能芯片等新兴技术领域的应用所面临的挑战与机遇。随着科技的飞速进步&#xff0c;新兴技…

websocket身份验证

websocket身份验证 前言 上一集我们就完成了websocket初始化的任务&#xff0c;那么我们完成这个内容之后就应该完成一个任务&#xff0c;当客户端与服务端连接成功之后&#xff0c;客户端应该主动发起一个身份认证的消息。 身份认证proto 我们看一眼proto文件的内容。 我…

Spire.PDF for .NET【页面设置】演示:复制 PDF 文档中的页面

在某些情况下&#xff0c;我们需要创建 PDF 文档中现有页面的副本&#xff0c;而不是复制整个文件&#xff0c;特别是如果我们必须创建某个页面的数百份副本&#xff0c;那么逐个复制页面可能会很繁琐。本文演示了如何使用 Spire.PDF 复制 PDF 文档中的页面并一次创建多个副本的…

Vue-组件三大组成组件通信

一、学习目标 1.组件的三大组成部分&#xff08;结构/样式/逻辑&#xff09; scoped解决样式冲突/data是一个函数 2.组件通信 组件通信语法 父传子 子传父 非父子通信&#xff08;扩展&#xff09; 3.综合案例&#xff1a;小黑记事本&#xff08;组件版&#xff09; 拆…

2024CVPR点云-1-点云分类CausalPC

文章摘要&#xff1a;深度神经网络在点云分类中表现出了显著的性能。然而&#xff0c;以前的工作表明它们容易受到对抗性扰动的影响&#xff0c;这些扰动可以操纵它们的预测。鉴于点云的独特模态&#xff0c;出现了各种攻击策略&#xff0c;这对现有的防御提出了挑战&#xff0…