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

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

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

文章目录

  • 思路
  • 解题方法
  • 复杂度
  • Code

思路

这个问题可以通过使用KMP(Knuth-Morris-Pratt)算法来解决。KMP算法是一种改进的字符串匹配算法,它的主要思想是当子串与目标字符串不匹配时,能知道一部分已经匹配的字符,利用这些信息避免从目标字符串的头部再去做匹配。

解题方法

KMP算法首先会预处理子串,生成一个名为next的数组,用于存储子串的最长公共前后缀的长度。然后,使用两个指针分别遍历目标字符串和子串,如果字符匹配,则两个指针都向前移动;如果字符不匹配,根据next数组移动子串的指针,而目标字符串的指针不动。如果子串的指针移动到了子串的末尾,那么就找到了一个匹配的子串。

复杂度

时间复杂度:

O ( n + m ) O(n+m) O(n+m),其中 n n n是目标字符串的长度, m m m是子串的长度。预处理子串的时间复杂度是 O ( m ) O(m) O(m),匹配的时间复杂度是 O ( n ) O(n) O(n)

空间复杂度:

O ( m ) O(m) O(m),需要额外的空间来存储 n e x t next next数组。

Code

class Solution {public int strStr(String s1, String s2) {return kmp(s1.toCharArray(), s2.toCharArray());}public int kmp(char[] s1, char[] s2) {int n = s1.length;int m = s2.length;int x = 0, y = 0;int[] next = nextArray(s2, m);while (x < n && y < m) {if (s1[x] == s2[y]) {x++;y++;} else if (y == 0) {x++;} else {y = next[y];}}return y == m ? x - y : -1;}public int[] nextArray(char[] s, int m) {if(m == 1) {return new int[]{-1};}int[] next = new int[m];next[0] = -1;next[1] = 0;int i = 2, cn = 0;while(i < m) {if(s[i - 1] == s[cn]) {next[i++] = ++cn;} else if(cn > 0) {cn = next[cn];} else {next[i++] = 0;}}return next;}
}

相关文章:

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

Problem: 28. 找出字符串中第一个匹配项的下标 文章目录 思路解题方法复杂度Code 思路 这个问题可以通过使用KMP&#xff08;Knuth-Morris-Pratt&#xff09;算法来解决。KMP算法是一种改进的字符串匹配算法&#xff0c;它的主要思想是当子串与目标字符串不匹配时&#xff0c;能…...

宿舍|学生宿舍管理小程序|基于微信小程序的学生宿舍管理系统设计与实现(源码+数据库+文档)

学生宿舍管理小程序目录 目录 基于微信小程序的学生宿舍管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 &#xff08;1&#xff09;学生信息管理 &#xff08;2&#xff09;公告信息管理 &#xff08;3&#xff09;宿舍信息管理 &am…...

CVE-2022-25487 漏洞复现

漏洞描述&#xff1a;Atom CMS 2.0版本存在远程代码执行漏洞&#xff0c;该漏洞源于/admin/uploads.php 未能正确过滤构造代码段的特殊元素。攻击者可利用该漏洞导致任意代码执行。 其实这就是一个文件上传漏洞罢了。。。。 打开之后&#xff0c;/home路由是个空白 信息搜集&…...

C#面:强类型和弱类型

强类型 强类型是指在编程语言中&#xff0c;变量必须明确声明其数据类型&#xff0c;并且在编译时会进行类型检查的特性。它可以提高代码的可读性和可维护性&#xff0c;但有时需要显式地进行类型转换。换句话说&#xff0c;强类型语言要求变量的类型在编译时就要确定&#xf…...

nodejs和npm和vite

Nodejs 简单的说 Node.js 就是运行在服务端的 JavaScript。 Node.js 是一个基于 Chrome JavaScript 运行时建立的一个平台。 Node.js 是一个事件驱动 I/O 服务端 JavaScript 环境 用途&#xff1a; Node.js 可以被看作是一个 JavaScript 运行时环境&#xff0c;专门用于在服务…...

相机图像质量研究(24)常见问题总结:CMOS期间对成像的影响--摩尔纹

系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

Redis -- 数据库管理

目录 前言 切换数据库(select) 数据库中key的数量&#xff08;dbsize&#xff09; 清除数据库&#xff08;flushall flushdb&#xff09; 前言 MySQL有一个很重要的概念&#xff0c;那就是数据库database&#xff0c;一个MySQL里面有很多个database&#xff0c;一个datab…...

蓝桥杯(Web大学组)2023省赛真题:视频弹幕

思路&#xff1a; 主要是要仔细阅读题目以及理解给出的已有代码&#xff0c;进行函数间的调用、定时器的使用、元素移除、清除定时器等&#xff0c;注意细节。 笔记&#xff1a; height不要写成hight设置left时,记得加单位px可以获取left的值进行计算&#xff0c;但要注意sp…...

真假难辨 - Sora(OpenAI)/世界模拟器的技术报告

目录 引言技术报告汉译版英文原版 引言 Sora是OpenAI在2024年2月15日发布的世界模拟器&#xff0c;功能是通过文本可以生成一分钟的高保真视频。由于较高的视频质量&#xff0c;引起了巨大关注。下面是三个示例&#xff0c;在示例之后给出了其技术报告&#xff1a; tokyo-wal…...

Linux第52步_移植ST公司的linux内核第4步_关闭内核模块验证和log信息时间戳_编译_并通过tftp下载测试

1、采用程序配置关闭“内核模块验证” 默认配置文件“stm32mp1_atk_defconfig”路径为“arch/arm/configs”; 使用VSCode打开默认配置文件“stm32mp1_atk_defconfg”&#xff0c;然后将下面的4条语句屏蔽掉&#xff0c;如下&#xff1a; CONFIG_MODULE_SIGy CONFIG_MODULE_…...

ctfshow-web21~28-WP

爆破(21-28) web21 题目给了一个zip文件,打开后解压是爆破的字典,我们抓包一下网址看看 发现账号和密码都被base64了,我们发送到intruder模块,给爆破的位置加上$符圈住 去base64解码一下看看格式...

鸿蒙开发系列教程(二十四)--List 列表操作(3)

列表编辑 1、新增列表项 定义列表项数据结构和初始化列表数据&#xff0c;构建列表整体布局和列表项。 提供新增列表项入口&#xff0c;即给新增按钮添加点击事件。 响应用户确定新增事件&#xff0c;更新列表数据。 2、删除列表项 列表的删除功能一般进入编辑模式后才可…...

线性代数笔记2--矩阵消元

0. 简介 矩阵消元 1. 消元过程 实例方程组 { x 2 y z 2 3 x 8 y z 12 4 y z 2 \begin{cases} x2yz2\\ 3x8yz12\\ 4yz2 \end{cases} ⎩ ⎨ ⎧​x2yz23x8yz124yz2​ 矩阵化 A [ 1 2 1 3 8 1 0 4 1 ] X [ x y z ] A \begin{bmatrix} 1 & 2 & 1 \\ 3 & …...

透光力之珠——光耦固态继电器的独特特点解析

光耦固态继电器作为现代电子控制领域中的重要组件&#xff0c;以其独特的特点在工业、通信、医疗等多个领域得到广泛应用。本文将深入剖析光耦固态继电器的特点&#xff0c;揭示其在电子控制中的卓越性能。 光耦固态继电器的光电隔离技术 光耦固态继电器以其光电隔离技术而脱颖…...

C#系列-​​​​​​​EntityFrameworkCore.Transactions.Abstractions应用场景+实例(38)

EntityFrameworkCore.Transactions.Abstractions应用场景 EntityFrameworkCore.Transactions.Abstractions 并不是一个官方的或广泛认可的 NuGet 包名称。在 Entity Framework Core (EF Core) 中&#xff0c;事务管理通常是通过 DbContext 的内置方法来实现的&#xff0c;如 Sa…...

PMDG 737

在Simbrief中生成计划后下载两个文件 放到C:\Users\32497\AppData\Local\Packages\Microsoft.FlightSimulator_8wekyb3d8bbwe\LocalState\packages\pmdg-aircraft-737(微软商店版本) 加油 先在飞行计划中查看计划燃油数量 MCDU中, AIRPLANE SEVICE 第二页, REQUEST FUEL TR…...

深入探索Midjourney:领航人工智能的新征程

深入探索Midjourney&#xff1a;领航人工智能的新征程 引言 在这个数据驱动、以技术创新为核心的时代&#xff0c;Midjourney以其独特的特性在人工智能领域中崭露头角。作为一款前沿的人工智能工具&#xff0c;它不仅重新定义了人机交互的方式&#xff0c;而且为各行各业提供…...

ChatGPT高效提问—prompt实践(漏洞风险分析-重构建议-识别内存泄漏)

ChatGPT高效提问—prompt实践&#xff08;漏洞风险分析-重构建议-识别内存泄漏&#xff09; 1.1 漏洞和风险分析 ChatGPT还可以帮助开发人员预测代码的潜在风险&#xff0c;识别其中的安全漏洞&#xff0c;而不必先运行它&#xff0c;这可以让开发人员及早发现错误&#xff0…...

【AIGC】Stable Diffusion 的提示词入门

一、正向提示词和反向提示词 Stable Diffusion 中的提示词通常用于指导用户对生成的图像进行控制。这些提示词可以分为正向提示词&#xff08;Positive Prompts&#xff09;和反向提示词&#xff08;Negative Prompts&#xff09;两类&#xff0c;它们分别影响图像生成过程中的…...

力扣---通配符匹配

题目描述&#xff1a; 给你一个输入字符串 (s) 和一个字符模式 (p) &#xff0c;请你实现一个支持 ? 和 * 匹配规则的通配符匹配&#xff1a; ? 可以匹配任何单个字符。 * 可以匹配任意字符序列&#xff08;包括空字符序列&#xff09;。 判定匹配成功的充要条件是&#xff…...

DNS负载均衡的5个认知误区:为什么你的轮询总不生效?(附排查指南)

DNS负载均衡的5个认知误区&#xff1a;为什么你的轮询总不生效&#xff1f;&#xff08;附排查指南&#xff09; 当我们在讨论DNS负载均衡时&#xff0c;常常会遇到一些根深蒂固的误解。这些误解不仅会影响系统设计决策&#xff0c;还可能导致运维人员在排查问题时走弯路。本文…...

Zemax光学设计(三)——从艾里斑到系统分辨率:衍射极限的实战解析

1. 艾里斑&#xff1a;光学的终极像素 当你用手机拍夜景时&#xff0c;为什么远处的路灯总变成模糊的光团&#xff1f;这背后隐藏着光学系统的基本限制——艾里斑。我在设计微型内窥镜镜头时&#xff0c;曾花了三周时间优化像差&#xff0c;最终却发现图像清晰度卡在一个无法突…...

嵌入式AI新篇章:Qwen3-ASR-0.6B在边缘计算设备上的部署与优化

嵌入式AI新篇章&#xff1a;Qwen3-ASR-0.6B在边缘计算设备上的部署与优化 1. 引言&#xff1a;当语音识别遇见边缘计算 想象一下&#xff0c;你对着一个巴掌大的智能音箱说话&#xff0c;它几乎在你话音落下的瞬间就理解了你的意思&#xff0c;并且完全不需要连接云端。或者&…...

2026学生免费用AI编程神器全攻略——白嫖不要白不要,大学生快来

好的&#xff0c;上一章刚教你用GitHub武装自己&#xff0c;筑起技术护城河&#xff0c;但光会搬砖&#xff08;敲命令&#xff09;还不够&#xff0c;你得学会“开高达”——用AI编程助手把效率拉满。 2026年了&#xff0c;如果还纯靠手打for循环和查API文档&#xff0c;那你…...

5个关键步骤:使用SMUDebugTool解决AMD Ryzen硬件调试难题

5个关键步骤&#xff1a;使用SMUDebugTool解决AMD Ryzen硬件调试难题 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址: https:/…...

实时口罩检测系统性能优化:从算法到工程全链路调优

实时口罩检测系统性能优化&#xff1a;从算法到工程全链路调优 1. 引言 在公共场所疫情防控中&#xff0c;实时口罩检测系统发挥着重要作用。但在实际部署中&#xff0c;很多开发者会遇到性能瓶颈&#xff1a;检测速度跟不上视频流帧率、GPU资源占用过高、误报漏报频发等问题…...

springboot+vue基于web的在线学习资源推荐的设计与实现

目录功能模块分析推荐系统功能交互功能设计后台管理功能技术实现要点项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作功能模块分析 用户管理模块 用户注册与登录&#xff1a;支持邮箱/手机号注册&#xff0c;提供密码找回功能…...

Stable Diffusion v1.5 Archive 镜像实测:5步完成部署,快速体验文生图

Stable Diffusion v1.5 Archive 镜像实测&#xff1a;5步完成部署&#xff0c;快速体验文生图 1. 开篇&#xff1a;为什么选择SD1.5 Archive版本 Stable Diffusion作为当前最热门的开源AI绘画模型&#xff0c;已经迭代了多个版本。其中v1.5作为经典版本&#xff0c;在图像质量…...

如何快速掌握Mermaid在线编辑器:面向初学者的完整可视化工具指南

如何快速掌握Mermaid在线编辑器&#xff1a;面向初学者的完整可视化工具指南 【免费下载链接】mermaid-live-editor Edit, preview and share mermaid charts/diagrams. New implementation of the live editor. 项目地址: https://gitcode.com/GitHub_Trending/me/mermaid-l…...

忍者像素绘卷镜像免配置部署:自动检测GPU型号并加载最优配置

忍者像素绘卷镜像免配置部署&#xff1a;自动检测GPU型号并加载最优配置 1. 产品概览&#xff1a;打破次元壁的像素艺术工作站 忍者像素绘卷是一款基于Z-Image-Turbo深度优化的图像生成工作站&#xff0c;专为像素艺术创作而设计。它将传统漫画创作与现代AI技术相结合&#x…...