LeetCode[28]找出字符串中第一个匹配项的下标(KMP版本)
思路:
一开始我使用暴力过的,但是感觉还是不完美,想学习一下KMP的写法,所以这篇笔记就来了,首先KMP算法就要先维护一个最长相等前后缀的一个数组(统称前缀表),那么这个数组为什么能找出相等字符串呢?因为这个前缀表是维护了当前模式串最长前后缀,一旦出现不相等的情况,就可以根据不相等的位置的前一个位置的下标的值,就是需要回退的次数。
我的理解就是先想KMP算法的时间复杂度,是O(n+m),那么就是一个串遍历一遍,给出的文本串遍历一遍,给出的模式串遍历一遍,所以通过时间复杂度就知道这道题大概的一个for循环的方向,肯定是先遍历模式串算出前缀表,然后再遍历文本串结合前缀表得出答案。其实这个前缀表就在两个字符串中找相等的字符串。
那么说说前缀表怎么算出来的,遍历模式串,然后再来个双指针,初始的时候,头指针指向前缀的头部,尾指针指向后缀的尾部。(注意:前缀-不包含尾指针就是前缀,后缀-不包含尾指针就是后缀)所以尾指针就是初始为1,头指针为0。
前缀表一共三步:
1.头尾指针不相等,那么说明现在前后缀不一样,那么就让头指针向前退一步,直到两个指针相等。
2. 头尾指针相等的时候,就是说明存在前后缀一样的值了,那么就让头指针往后走一步。
3. 最后就是更新前缀表的值,遍历模式串的是i,所以next[i] = j,j就代表了当前最长相等的前后缀的个数。
通过拿到的前缀表,我们再对文本串进行遍历,就可以得到当前相等串的第一个下标了,详细的看代码和代码随想录的解释。
代码:
class Solution {public int strStr(String haystack, String needle) {if (needle.length() == 0)return 0;int[] next = new int[needle.length()];getNext(next, needle);int j = 0;for (int i = 0; i < haystack.length(); i++) {while (j > 0 && needle.charAt(j) != haystack.charAt(i)) {j = next[j - 1];}if (needle.charAt(j) == haystack.charAt(i)) {j++;}if (j == needle.length()) {return i - needle.length() + 1;}}return -1;}public void getNext(int[] next, String s) {int j = 0;next[0] = 0;for (int i = 1; i < s.length(); i++) {while (j > 0 && s.charAt(j) != s.charAt(i)) {j = next[j - 1];}if (s.charAt(j) == s.charAt(i)) {j++;}next[i] = j;}}
}
相关文章:
LeetCode[28]找出字符串中第一个匹配项的下标(KMP版本)
思路: 一开始我使用暴力过的,但是感觉还是不完美,想学习一下KMP的写法,所以这篇笔记就来了,首先KMP算法就要先维护一个最长相等前后缀的一个数组(统称前缀表),那么这个数组为什么能找…...
Cesium实现雨、闪电、雪、雾天气效果
基于 Cesium 的三维地理信息场景,集成了天气效果后处理、3D 模型加载、水域渲染等功能。以下是详细功能总结: 1. 场景初始化与基础配置 三维地球初始化 创建 Cesium Viewer 实例,隐藏默认控件(时间轴、动画控件等)&…...
上门送水小程序区域代理模块框架设计
一、逻辑分析 代理申请流程: 潜在代理商通过小程序提交代理申请,需要填写个人或企业基本信息、联系方式、期望代理区域等。系统收到申请后,进行初步审核,检查信息的完整性和合规性。运营人员进行人工审核,根据公司政策…...
GIS开发笔记(6)结合osg及osgEarth实现半球形区域绘制
一、实现效果 输入中心点坐标及半径,绘制半球形区域,地下部分不显示。 二、实现原理 根据中心点及半径绘制半球形区域,将其挂接到地球节点。 三、参考代码 void GlobeWidget::drawSphericalRegion(osg::Vec3d point,double radius) {// 使…...
UE5在场景3D物体上播放本地视频(带声音)
UE5在场景3D物体上播放本地视频(带声音) 0.在Map中创建一个立方体,调整大小看起来像屏幕一样 1.创建文件夹Movies在根目录下 2.把准备的视频复制到Movies文件夹下 3.把Movies文件夹下的视频拖入到UE自己创建的文件夹下,此时会有个文件媒体源…...
安装部署RabbitMQ
一、RabbitMQ安装部署 1、下载epel源 2、安装RabbitMQ 3、启动RabbitMQ web管理界面 启用插件 rabbitmq数据目录 创建rabbitmq用户 设置为管理员角色 给用户赋予权限 4、访问rabbitmq...
STM32启动流程详解
STM32启动流程详解 本文档详细介绍STM32微控制器从上电到main函数执行的完整启动流程。 1. 上电与复位过程 当STM32芯片上电或复位时,硬件会执行以下步骤: 上电复位(POR)/低电平复位(PDR): 芯片接通电源或NRST引脚置低时触发初始PC值设置: 程序计数器…...
【正点原子STM32MP257连载】第四章 ATK-DLMP257B功能测试——CPU温度CPU主频
1)实验平台:正点原子ATK-DLMP257B开发板 2)浏览产品:https://www.alientek.com/Product_Details/135.html 3)全套实验源码手册视频下载:正点原子资料下载中心 第四章 ATK-DLMP257B功能测试——CPU主频&…...
LVDS系列8:Xilinx 7系可编程输入延迟(一)
在解析LVDS信号时,十分重要的一环就是LVDS输入信号线在经过PCB输入到FPGA中后,本来该严格对齐的信号线会出现时延,所以需要在FPGA内部对其进行延时对齐后再进行解析。 Xilinx 7系器件中用于输入信号延时的组件为IDELAYE2可编程原语࿰…...
iotdb时序数据库使用
iotdb https://github.com/apache/iotdb.git 安装maven3.9.6以上版本执行编译 iotdb启动,使用安装包sbin目录下的start-standalone.bat sbin\start-standalone.bat 执行报错如果是内存问题,可以在对应的node配置中修改,如conf\datanode-ev…...
【Caddy】:现代化、自动 HTTPS 的 Web 服务器新星
🚀 Caddy:现代化、自动 HTTPS 的 Web 服务器新星! 在构建和部署 Web 应用时,你可能听说过或用过如 Nginx、Apache 等经典的 Web 服务器。但在今天,有一个越来越受欢迎的新选择——Caddy。 本文将带你认识 Caddy&…...
用 DeepSeek 精准解析,PDF 一键转电子书!
经常需要阅读大量的 PDF 文档,但在移动设备上阅读 PDF 通常体验极差。屏幕小、排版固定,需要不断放大缩小,眼睛容易疲劳,长时间阅读简直是一种折磨。 虽有不少 PDF 转换工具,但对扫描书籍支持不佳,经常丢失…...
【AIoT】智能硬件GPIO通信详解(二)
前言 上一篇我们深入解析了智能硬件GPIO通信原理(传送门:【AIoT】智能硬件GPIO通信详解(一))。接下来,我们将结合无人售货机控制场景,通过具体案例进一步剖析物联网底层通信机制的实际应用。 在智能零售领域,无人售货机通过AI技术升级为智能柜,其设备控制的底层通信…...
Mac OS系统下kernel_task占用大量CPU资源导致系统卡顿
CPU负载突然飙升,如截图: 根本原因,大家从各种博主上已知晓,现在提供自己的解决办法,亲测有效 一、设置开机自动禁用温度管理守护进程 1.创建脚本文件 mkdir -p ~/Scripts touch ~/Scripts/disable_thermald.sh …...
镜舟科技助力某大型电网企业破解数据架构升级难题,打造国产化湖仓标杆
在 “十四五” 规划全面推进国产化替代的背景下,某大型电网企业联合镜舟科技与腾讯云,基于全球领先的开源分析型数据库 StarRocks 及腾讯 TBDS 大数据平台,构建电力行业国产化湖仓一体架构。该项目实现 PB 级电力数据的统一管理,为…...
Linux内核内存管理单元 详解Linux 内核伙伴系统(Buddy System)的快速路径分配函数get_page_from_freelist
一、函数核心作用 get_page_from_freelist 是 Linux 内核伙伴系统(Buddy System)的快速路径分配函数,负责从指定的内存区域(Zone)中高效分配连续的物理内存页。其核心逻辑是遍历允许的 Zone 列表,检查水位…...
网络原理 - 初识网络 2
目录 OSI 七层协议 TCP / IP 五层模型 网络设备所在分层 网络分层对应 封装和分用(网络传输数据过程中,最核心的流程) 用一个具体例子来梳理以下封装和分用的过程 封装 1. 应用层(应用程序) -- QQ 2. 传输层 …...
如何利用GM DC Monitor快速监控一台网络类设备
GM DC Monitor v2.0在网络类设备监控的效率非常高! 如果您需要管理运维大量的网络类设备,GM DC Monitor是个不错的选择。 如果您具备一定的采集脚本编写能力,可以在平台的定制属于自己的监控模板! 1)首先建立数据中…...
类和对象终
一、初始化列表 再谈构造函数 我们之前实现构造函数的时候,初始化成员变量在函数体内赋值的,构造函数还有一种初始化方式,就是初始化列表 我们先实现一个栈来举例: // 实现一个栈 typedef int DataType; class Stack { public:…...
教程:批量提取图片pdf固定位置文字然后保存为新的文件名,基于Python和阿里云的实现方案
一、项目背景 在实际工作和生活中,存在大量需要对图片或 PDF 进行批量处理的场景。例如,在档案管理中,工作人员可能会扫描大量文件,生成图片或 PDF 格式的档案资料。这些资料通常包含特定位置的关键信息,如文件编号、日期等。通过批量提取这些关键信息并将其作为文件名,…...
JVM:堆、方法区
一、堆 概念:堆用于存储对象和数组,主要分为新生代和老年代,新生代又细分为伊甸园区、幸存者 0 区(S0)和幸存者 1 区(S1)内存设置:可用 -Xmx 和 -Xms 设置堆内存大小,-X…...
JVM-基于Hotspot
前言 Java虚拟机(Java Virtual Machine简称JVM)是运行所有Java程序的抽象计算机,是Java语言的运行环境,其主要任务为将字节码装载到内部,解释/编译为对应平台上的机器指令执行。 Java虚拟机规范定义了一个抽象的——…...
Android 10.0 第三方Launcher设置默认Launcher后导致Recent最近任务键无效
1.前言 在10.0的系统rom定制化开发中,在进入launcher的定制过程中,在某些产品中,需要设置第三方launcher为默认Launcher功能, 所以在设置以后,会发现最近recent键无效,所以接下来需要分析相关流程来实现相关功能的实现 2.第三方Launcher设置默认Launcher后导致Recent最…...
状态模式详解与真实场景案例(Java实现)
模式定义 状态模式(State Pattern) 允许对象在其内部状态改变时改变它的行为,使对象看起来像是修改了它的类。属于行为型设计模式,核心思想是将状态抽象为独立对象,不同状态下行为封装在不同状态类中。 解决的问题 …...
uniapp-商城-26-vuex 使用流程
为了能在所有的页面都实现状态管理,我们按照前面讲的页面进行状态获取,然后再进行页面设置和布局,那就是重复工作,vuex 就会解决这样的问题,如同类、高度提炼的接口来帮助我们实现这些重复工作的管理。避免一直在造一样的轮子。 https://vuex.vuejs.org/zh/#%E4%BB%80%E4…...
科技快讯 | 智谱开源最新GLM模型系列;“AI 洗头店”现身广州;ChatGPT上线图库功能
智谱开源最新GLM模型系列,启用全球域名“Z.ai” 4月15日,智谱开源最新GLM模型系列,包括32B和9B尺寸,涵盖基座、推理、沉思三类模型,全部遵循MIT开源许可协议。推理模型GLM-Z1-32B-0414实测推理速度达200 tokens/秒&…...
LeetCode 2537.统计好子数组的数目:滑动窗口(双指针)
【LetMeFly】2537.统计好子数组的数目:滑动窗口(双指针) 力扣题目链接:https://leetcode.cn/problems/count-the-number-of-good-subarrays/ 给你一个整数数组 nums 和一个整数 k ,请你返回 nums 中 好 子数组的数目。 一个子数组 arr 如果…...
精益数据分析(1/126):从《精益数据分析》探寻数据驱动增长之道
精益数据分析(1/126):从《精益数据分析》探寻数据驱动增长之道 在当今数字化时代,数据无疑是企业发展的关键驱动力,对于竞争激烈的程序化广告行业更是如此。最近我在研读《精益数据分析》这本书,收获颇丰&…...
uniapp-商城-27-vuex 通用方法
1 概述 上节说了vuex 的基本使用方法,分析了基本的使用方法。 在使用中,常见使用,我们要针对状态,购物车,不同类事务的管理,如果按照上节课的通用方法,那么使用和维护是会很大的难度的。 所以这里就必须要进行处理,借助 modules 进行定义不同类事务的处理手段。便于…...
MetaLiveX:用AI重新定义直播互动的边界
“直播的核心价值,在于它能否让观众从‘旁观者’变为‘共創者’。”在近期一场数字技术峰会上,杜子程(Emma Zicheng Du)首次公开阐释了其团队研发的MetaLiveX平台核心理念。这一以AI为驱动的智能直播系统,正通过动态场景生成与情感化交互设计,重新定义虚拟社群的参与逻辑。目前…...
线程安全学习
1 什么是线程 线程是cpu调度的最小单位,在Linux 下 实现线程的方式为轻量级进程,复用进程的结构体,使用clone函数创建 2 线程安全 所谓线程安全,更确切的应该描述为内存安全 #include <stdio.h> #include <pthread.h…...
三层路由器,SSH远程登录访问路由器,通过telnet远程登录访问路由器(不安全),路由器的基本设置之多网络互联解决办法:单臂路由
三层路由器 默认路由器端口关闭:no shutdown (开启)需进入端口默认路由开启:无需 ip routing路由器充当网关,可以连接不同网络接口种类丰富,数量少 SSH远程登录访问路由器 记得设IP Would you like to e…...
分布式光伏电站运维难?Acrel-1000DP助力安全稳定运行
针对用户新能源接入后存在安全隐患、缺少有效监控、发电效率无法保证、收益计算困难、运行维护效率低等通点,提出的Acrel-1000DP分布式光伏监控系统平台,对整个用户电站全面监控,为用户实现降低能源使用成本、减轻变压器负载、余电上网&#…...
基于sherpa-onnx 安卓语音识别尝鲜
sherpa-onnx简介 Sherpa:是一个由 K2-FSA 团队 开发的 开源语音处理框架,旨在解决传统语音识别工具(如 Kaldi)在模型部署和跨平台适配中的复杂性问题。它通过整合现代深度学习技术和高效推理引擎,提供了从语音识别、合…...
利用 Python 和 AI 技术创作独特的图像艺术作品
1. 项目目标 生成艺术作品:利用 AI 模型(如 Stable Diffusion)生成具有艺术风格的图像。自定义风格:通过文本提示(prompt)控制图像的艺术风格(如赛博朋克、印象派、超现实主义等)。…...
Web自动化测试的详细流程和步骤
🍅 点击文末小卡片,免费获取软件测试全套资料,资料在手,涨薪更快 Web自动化测试是软件测试中非常重要的一种测试方法,它通过编写脚本来模拟人工操作网页,从而实现对Web应用程序进行自动化测试的过程。为了保…...
记录一个坑关于STM32 ARM Compiler Version
在用 Keil 进行 STM32 开发的时候,一开始下载,下载的 ARM 编译器是 Version6,他就不兼容老的代码,就很抽象。 所以必须要更换编译器。 可以去官网下载编译器 Downloads - Arm Developer ,也可以自己找资源哈ÿ…...
TCP实现多线程远程命令执行
1.上一篇篇代码改进 bind的绑定第一个是对象,其余的都是参数,传给一个类需要this指针,所以有&r 错误地方是智能指针的参数要加&,thread.name()要删除 2.介绍需要用到函数 popen函数 FILE *popen(const char *command, …...
【MySQL】索引特性
文章目录 👉没有索引可能会有什么问题👈👉认识磁盘👈前置知识MySQL 与磁盘磁盘定位扇区结论磁盘随机访问与连续访问MySQL 与磁盘交互基本单位 👉MySQL 的整体轮廓👈👉索引的理解👈建…...
红宝书第四十七讲:Node.js服务器框架解析:Express vs Koa 完全指南
红宝书第四十七讲:Node.js服务器框架解析:Express vs Koa 完全指南 资料取自《JavaScript高级程序设计(第5版)》。 查看总目录:红宝书学习大纲 一、框架定位:HTTP服务器的工具箱 共同功能: 快…...
SDK游戏盾ip可以破解吗
从技术实现和法律合规性角度,不建议也不应尝试破解SDK游戏盾的IP防护机制。以下是详细分析: 一、法律与道德风险 违法行为 破解游戏盾的IP防护属于非法侵入计算机信息系统或破坏网络安全的行为,可能…...
eBay东南亚爆单密码:72小时交付计划如何重构厦门仓+东南亚供应链?
2024年东南亚电商市场规模预计突破2340亿美元,年复合增长率达18%。eBay最新战略将厦门纳入海外仓核心节点,推出“72小时交付计划”,通过“仓配转”一体化链路,助力中国卖家实现东南亚市场订单履约率提升10%,退货成本降…...
大语言模型
1.当前有哪些主流AI方向 1.1大语言模型方向 OpenAI的GPT语言模型系列,o3等推理模型系列 综合能力强 anthrotic的claude系列,推理预测混合模型 代码能力强 DeepSeek的V系列,R1推理模型 …...
深入理解Java缓冲输入输出流:性能优化的核心武器
在Java应用程序的IO操作中,频繁的磁盘读写或网络传输往往是性能瓶颈的主要来源。JDK提供的缓冲流(Buffered Streams)通过内存缓冲机制,将零碎的IO操作转化为批量处理,成为提升IO效率的关键技术。本文将从设计原理、核心机制到实战技巧,全面解析缓冲流的技术细节。 一、缓…...
AI 对话高效输入指令攻略(一):了解AI对话指令
目录 引 一.认识 AI 对话中的指令基础 1.运行原理 2.智能体在 AI 对话中的关键角色与运行机制 3.智能体的核心任务 4.对不同指令的响应差异 5.针对不同指令类型的处理方式 6.智能体在底层逻辑中的运作 二.高效输入指令的底层逻辑 1.语义匹配逻辑 …...
AI大模型从0到1记录学习 数据结构和算法 day19
常用算法 查找算法 二分查找 算法原理 二分查找又称折半查找,适用于有序列表。其利用数据的有序性,每轮缩小一半搜索范围,直至找到目标元素或搜索区间为空为止。 代码实现 def binary_search(arr, target): left, right 0, len(arr) - 1 w…...
Python + Playwright:使用正则表达式增强自动化测试
Python + Playwright:使用正则表达式增强自动化测试 前言一、 为什么选择正则表达式?二、 Playwright 中集成正则表达式:途径与方法三、 实战应用:正则表达式解决典型测试难题场景 1:定位 ID 或 Class 包含动态部分的元素场景 2:验证包含可变数字或文本的提示信息场景 3:…...
构建用户友好的记账体验 - LedgerX交互设计与性能优化实践
构建用户友好的记账体验 - LedgerX交互设计与性能优化实践 发布日期: 2025-04-16 引言 在财务管理应用领域,技术实力固然重要,但最终决定用户留存的往往是日常使用体验。本文作为LedgerX技术博客的第二篇,将深入探讨我们如何通过精心的交互…...
AI赋能PLC(一):三菱FX-3U编程实战初级篇
前言 在工业自动化领域,三菱PLC以其高可靠性、灵活性和广泛的应用场景,成为众多工程师的首选控制设备。然而,传统的PLC编程往往需要深厚的专业知识和经验积累,开发周期长且调试复杂。随着人工智能技术的快速发展,利用…...
人工智能——梯度提升决策树算法
目录 摘要 14 梯度提升决策树 14.1 本章工作任务 14.2 本章技能目标 14.3 本章简介 14.4 编程实战 14.5 本章总结 14.6 本章作业 本章已完结! 摘要 本章实现的工作是:首先采用Python语言读取含有英语成绩、数学成绩以及学生所属类型的样本数据…...