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(Knuth-Morris-Pratt)算法来解决。KMP算法是一种改进的字符串匹配算法,它的主要思想是当子串与目标字符串不匹配时,能…...
宿舍|学生宿舍管理小程序|基于微信小程序的学生宿舍管理系统设计与实现(源码+数据库+文档)
学生宿舍管理小程序目录 目录 基于微信小程序的学生宿舍管理系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、管理员模块的实现 (1)学生信息管理 (2)公告信息管理 (3)宿舍信息管理 &am…...
CVE-2022-25487 漏洞复现
漏洞描述:Atom CMS 2.0版本存在远程代码执行漏洞,该漏洞源于/admin/uploads.php 未能正确过滤构造代码段的特殊元素。攻击者可利用该漏洞导致任意代码执行。 其实这就是一个文件上传漏洞罢了。。。。 打开之后,/home路由是个空白 信息搜集&…...
C#面:强类型和弱类型
强类型 强类型是指在编程语言中,变量必须明确声明其数据类型,并且在编译时会进行类型检查的特性。它可以提高代码的可读性和可维护性,但有时需要显式地进行类型转换。换句话说,强类型语言要求变量的类型在编译时就要确定…...
nodejs和npm和vite
Nodejs 简单的说 Node.js 就是运行在服务端的 JavaScript。 Node.js 是一个基于 Chrome JavaScript 运行时建立的一个平台。 Node.js 是一个事件驱动 I/O 服务端 JavaScript 环境 用途: Node.js 可以被看作是一个 JavaScript 运行时环境,专门用于在服务…...
相机图像质量研究(24)常见问题总结:CMOS期间对成像的影响--摩尔纹
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...
Redis -- 数据库管理
目录 前言 切换数据库(select) 数据库中key的数量(dbsize) 清除数据库(flushall flushdb) 前言 MySQL有一个很重要的概念,那就是数据库database,一个MySQL里面有很多个database,一个datab…...
蓝桥杯(Web大学组)2023省赛真题:视频弹幕
思路: 主要是要仔细阅读题目以及理解给出的已有代码,进行函数间的调用、定时器的使用、元素移除、清除定时器等,注意细节。 笔记: height不要写成hight设置left时,记得加单位px可以获取left的值进行计算,但要注意sp…...
真假难辨 - Sora(OpenAI)/世界模拟器的技术报告
目录 引言技术报告汉译版英文原版 引言 Sora是OpenAI在2024年2月15日发布的世界模拟器,功能是通过文本可以生成一分钟的高保真视频。由于较高的视频质量,引起了巨大关注。下面是三个示例,在示例之后给出了其技术报告: tokyo-wal…...
Linux第52步_移植ST公司的linux内核第4步_关闭内核模块验证和log信息时间戳_编译_并通过tftp下载测试
1、采用程序配置关闭“内核模块验证” 默认配置文件“stm32mp1_atk_defconfig”路径为“arch/arm/configs”; 使用VSCode打开默认配置文件“stm32mp1_atk_defconfg”,然后将下面的4条语句屏蔽掉,如下: CONFIG_MODULE_SIGy CONFIG_MODULE_…...
ctfshow-web21~28-WP
爆破(21-28) web21 题目给了一个zip文件,打开后解压是爆破的字典,我们抓包一下网址看看 发现账号和密码都被base64了,我们发送到intruder模块,给爆破的位置加上$符圈住 去base64解码一下看看格式...
鸿蒙开发系列教程(二十四)--List 列表操作(3)
列表编辑 1、新增列表项 定义列表项数据结构和初始化列表数据,构建列表整体布局和列表项。 提供新增列表项入口,即给新增按钮添加点击事件。 响应用户确定新增事件,更新列表数据。 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 & …...
透光力之珠——光耦固态继电器的独特特点解析
光耦固态继电器作为现代电子控制领域中的重要组件,以其独特的特点在工业、通信、医疗等多个领域得到广泛应用。本文将深入剖析光耦固态继电器的特点,揭示其在电子控制中的卓越性能。 光耦固态继电器的光电隔离技术 光耦固态继电器以其光电隔离技术而脱颖…...
C#系列-EntityFrameworkCore.Transactions.Abstractions应用场景+实例(38)
EntityFrameworkCore.Transactions.Abstractions应用场景 EntityFrameworkCore.Transactions.Abstractions 并不是一个官方的或广泛认可的 NuGet 包名称。在 Entity Framework Core (EF Core) 中,事务管理通常是通过 DbContext 的内置方法来实现的,如 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:领航人工智能的新征程 引言 在这个数据驱动、以技术创新为核心的时代,Midjourney以其独特的特性在人工智能领域中崭露头角。作为一款前沿的人工智能工具,它不仅重新定义了人机交互的方式,而且为各行各业提供…...
ChatGPT高效提问—prompt实践(漏洞风险分析-重构建议-识别内存泄漏)
ChatGPT高效提问—prompt实践(漏洞风险分析-重构建议-识别内存泄漏) 1.1 漏洞和风险分析 ChatGPT还可以帮助开发人员预测代码的潜在风险,识别其中的安全漏洞,而不必先运行它,这可以让开发人员及早发现错误࿰…...
【AIGC】Stable Diffusion 的提示词入门
一、正向提示词和反向提示词 Stable Diffusion 中的提示词通常用于指导用户对生成的图像进行控制。这些提示词可以分为正向提示词(Positive Prompts)和反向提示词(Negative Prompts)两类,它们分别影响图像生成过程中的…...
力扣---通配符匹配
题目描述: 给你一个输入字符串 (s) 和一个字符模式 (p) ,请你实现一个支持 ? 和 * 匹配规则的通配符匹配: ? 可以匹配任何单个字符。 * 可以匹配任意字符序列(包括空字符序列)。 判定匹配成功的充要条件是ÿ…...
重塑机械键盘体验:ZMK固件的革新之旅与实践指南
重塑机械键盘体验:ZMK固件的革新之旅与实践指南 【免费下载链接】zmk ZMK Firmware Repository 项目地址: https://gitcode.com/gh_mirrors/zm/zmk 在机械键盘的世界里,固件如同键盘的灵魂,决定着它的响应速度、功能拓展性和个性化程度…...
Wan2.2-I2V-A14B镜像免配置:SSH直连后cd /workspace即可执行全部命令
Wan2.2-I2V-A14B镜像免配置:SSH直连后cd /workspace即可执行全部命令 1. 镜像概述与核心优势 Wan2.2-I2V-A14B私有部署镜像是一款专为文生视频模型定制的开箱即用解决方案。这个镜像最大的特点就是"免配置"——通过SSH连接后,只需进入/works…...
告别格式枷锁:ncmdumpGUI让音乐自由播放变得触手可及
告别格式枷锁:ncmdumpGUI让音乐自由播放变得触手可及 【免费下载链接】ncmdumpGUI C#版本网易云音乐ncm文件格式转换,Windows图形界面版本 项目地址: https://gitcode.com/gh_mirrors/nc/ncmdumpGUI 开篇痛点直击:那些被NCM格式困住的…...
深入解析STM32与FreeRTOS内存管理:从理论到实践的最佳配置策略
1. STM32内存结构深度剖析 第一次接触STM32内存管理时,我也被那些专业术语搞得晕头转向。直到把开发板跑死机十几次后,才真正理解RAM和Flash的区别。简单来说,RAM就像你的办公桌面,随时可以读写但断电就清空;Flash则是…...
在模具设计领域,结构受压变形分析就像给钢铁骨架做“压力测试“。COMSOL的稳态研究模块能快速完成这类强度验证,但实际操作中有几个魔鬼细节需要特别注意
用comsol软件进行结构的受压变形分析,计算结构受压时应力分布及应变情况,预测模具的强度是否符合要求。 模型采用装配体,可以使用稳态研究,加快计算速度,在各零件接触的面设置接触对,对顶针施加位移&#x…...
DAMO-YOLO实战:搭建教育科研AI视觉实验平台
DAMO-YOLO实战:搭建教育科研AI视觉实验平台 1. 教育科研中的AI视觉需求 在教育科研领域,视觉AI技术正成为重要的研究工具。传统计算机视觉实验平台往往面临部署复杂、性能有限、交互体验差等问题。DAMO-YOLO智能视觉探测系统为解决这些问题提供了创新方…...
使用Chandra构建数学建模助手:美赛备战全攻略
使用Chandra构建数学建模助手:美赛备战全攻略 1. 引言 数学建模竞赛就像一场智力马拉松,需要在有限时间内解决复杂问题。每年美赛期间,无数团队熬夜奋战,只为找到最优解决方案。但现实往往是:选题纠结、算法选择困难…...
从零搭建无人船:两年实战后,我总结的ArduPilot+Pixhawk避坑全流程
从零搭建无人船:两年实战后,我总结的ArduPilotPixhawk避坑全流程 第一次把无人船放进水里时,GPS信号突然丢失,船体在河中央失控打转——这个惊心动魄的瞬间让我意识到,开源飞控的实战应用远不是下载代码、连接硬件那么…...
从零构建树莓派人脸识别门禁:硬件选型、环境部署与实战避坑
1. 硬件选型与采购清单 第一次玩树莓派人脸识别项目时,我在淘宝上花了整整三天对比各种硬件参数。当时最纠结的就是摄像头模块——普通USB摄像头才30块钱,而官方推荐的Raspberry Pi Camera Module V2要200多。后来实测发现,这差价真不能省。 …...
3分钟快速上手AdGuard浏览器扩展:开源广告拦截工具全平台安装指南
3分钟快速上手AdGuard浏览器扩展:开源广告拦截工具全平台安装指南 【免费下载链接】AdguardBrowserExtension AdGuard browser extension 项目地址: https://gitcode.com/gh_mirrors/ad/AdguardBrowserExtension AdGuard浏览器扩展是一款开源、免费的广告拦截…...
