代码随想录-字符串-实现strStr()--KMP

题目描述

思路:典型的数据结构中的KMP算法实现

代码与解析

假设两个字符串长度分别为m和n,暴力解则为O(m*n)

引入KMP算法降低时间复杂度,求next数组是O(m) 遍历匹配串是O(n)

KMP关键思路

①求出模式串的next数组,即最长公共前后缀的长度。前缀定义,不含最后一个字母,后缀定义不含第一个字母。

next[i] 代表第i个位置的最长公共前后缀的长度

这里定义next[0]=0,即第一个字母的最长公共前后缀长度都是0

遍历模式串

j代表模式串中i位置的最长前后缀长度为j,所以不配的时候回退为next[j-1]

private static 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;}}

模式串与匹配串

public static int strStr(String haystack, String needle) {if (needle.isEmpty()) 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;
}

整体KMP代码

class Solution {public int strStr(String haystack, String needle) {if (needle.isEmpty())return 0;// 字符串的模式匹配int length = needle.length();int[] next = new int[length];getNext(next, needle);// System.out.println(Arrays.toString(next));int j = 0;// j 来对子串操作 i来操作匹配串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++;}//模式串到头了,j应该是最后一个字符之后又加一了,所以j==length,而不是length-1if(j == length){return i-length+1;}}return -1;}// 构建next数组,用kmp算法实现此功能private void getNext(int[] next, String needle) {int j = 0;// 最长相等前后缀长度 不算第一个和最后一个字母,所以对于第一个位置,公共长度是0next[0] = j;for (int i = 1; i < next.length; i++) {while (j > 0 && needle.charAt(i) != needle.charAt(j)) {// 其实这里比较的是i和j都向公共前后缀子串后移动了一个之后的位置// 不相等,回退 j是公共长度,所以应该回退到 next[j-1] 这个之前的是可能相交的公共子串部分j = next[j - 1];}if (needle.charAt(i) == needle.charAt(j)) {j++;}next[i] = j;}}
}

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

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

相关文章

unity3d————叉乘练习题

代码示例&#xff1a; public class text: MonoBehaviour {public Transform A;public Transform B;private float dotResult;private Vector3 crossResult;void Update(){dotResult Vector3.Dot(A.forward, B.position - A.position);crossResult Vector3.Cross(A.forward,…

【VSCode插件推荐】想准时下班,你需要codemoss的帮助,分享AI写代码的愉快体验,附详细安装教程

在快节奏的开发环境中&#xff0c;如何高效地完成工作、提高生产力&#xff0c;成为了每位开发者的追求。今天&#xff0c;我将为大家介绍一款强大的VSCode插件——CodeMoss&#xff0c;它不仅能帮助你提高编程效率&#xff0c;还能让你享受到AI写代码的乐趣。 AI 问答&#xf…

[复健计划][紫书]Chapter 7 暴力求解法

7.1 简单枚举 例7-1 Division uva725 输入正整数n&#xff0c;按从小到大的顺序输出所有形如abcde/fghij n的表达式&#xff0c;其中a&#xff5e;j恰好为数字0&#xff5e;9的一个排列&#xff08;可以有前导0&#xff09;&#xff0c;2≤n≤79。枚举fghij&#xff0c;验证a…

【大数据技术基础 | 实验七】HBase实验:部署HBase

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤&#xff08;一&#xff09;验证Hadoop和ZooKeeper已启动&#xff08;二&#xff09;修改HBase配置文件&#xff08;三&#xff09;启动并验证HBase 六、实验结果七、实验心得 一、实验目的 掌握…

硬件知识10 线性稳压电源——二极管稳压、射级跟随器稳压、集成电路稳压

目录 一、相关理论 二、二极管稳压电路 1、理论与计算 2、不足 三、射级跟随器稳压电路 四、集成电路稳压器 1、78 79系列 2、LM317 LM337系列 3、功耗计算 一、相关理论 前文已进行了AC到DC的转换&#xff0c;只不过这个DC效果一般&#xff0c;因此需要用到稳压&…

查询引擎的演变之旅 | OceanBase原理解读

在关系型数据库中&#xff0c;查询调度器与计划执行器&#xff0c;有着与查询优化器同样重要的地位&#xff0c;随着计算机硬件技术的飞速进步&#xff0c;这两大模块的重要性日益凸显&#xff0c;成为提升数据库性能的关键所在。接下来&#xff0c;本文将由来自 OceanBase 的技…

【MFC编程(一)】MFC概述

文章目录 MFC概述MFC组成MFC对比Windows APIMFC类库基类CObject命令发送类CCmdTarget应用程序结构类应用程序线程支持类CWinThread/CWinApp文档类CDocument文档模板类CDocTemplate 窗口类窗口基类CWnd边框窗口类CFrameWnd视图类CView MFC概述 MFC&#xff08;Microsoft Founda…

深度学习基础—循环神经网络的梯度消失与解决

引言 深度学习基础—循环神经网络&#xff08;RNN&#xff09;https://blog.csdn.net/sniper_fandc/article/details/143417972?fromshareblogdetail&sharetypeblogdetail&sharerId143417972&sharereferPC&sharesourcesniper_fandc&sharefromfrom_link深…

并查集算法详解

文章目录 并查集概念并查集的常见操作构建并查集合并并查集和查找 关于find函数 并查集概念 并查集&#xff08;Union-Find&#xff09;是一种树型的数据结构&#xff0c;用于处理一些不交集的合并及查询问题。其主要应用是判断两个元素是否在同一个集合中&#xff0c;以及合并…

新书速览|Java网络爬虫精解与实践

《Java网络爬虫精解与实践》 本书内容 《Java网络爬虫精解与实践》全面而系统地介绍与网络爬虫程序相关的理论知识&#xff0c;并包含大量的实践操作案例。 《Java网络爬虫精解与实践》共分为 8 章。第 1 章以自动化框架为基础&#xff0c;介绍网络爬虫程序的入门开发实践。第…

多模态大模型微调实践!PAI+LLaMA Factory搭建AI导游

一、引言 AI的快速发展推动了各行各业的智能化转型和创新&#xff0c;随之而来的是对AI应用的迫切需求。 如何微调大模型、高效搭建AI应用成为了开发者们广泛关注的技术方向。阿里云人工智能平台PAI&#xff0c;联合开源低代码大模型微调框架LLaMA Factory &#xff0c;共同打…

提升安全上网体验:Windows 11 启用 DOH(阿里公共DNS)

文章目录 阿里公共 DNS 介绍免费开通云解析 DNS 服务Windows 编辑 DNS 设置配置 IPv4配置 IPv6 路由器配置 DNS 阿里公共 DNS 介绍 https://alidns.com/ 免费开通云解析 DNS 服务 https://dnsnext.console.aliyun.com/pubDNS 开通服务后&#xff0c;获取 DOH 模板&#xff0…

[C语言]strstr函数的使用和模拟实现

1.strstr函数的使用 char * strstr ( const char *str1, const char * str2); 返回一个指向str1中str2第一次出现的指针&#xff0c;如果str2中没有str1则返回 NULL。。 实例&#xff1a; #include <stdio.h> #include <string.h> int main() {char str[] "…

【HTML】——VSCode 基本使用入门和常见操作

阿华代码&#xff0c;不是逆风&#xff0c;就是我疯 你们的点赞收藏是我前进最大的动力&#xff01;&#xff01; 希望本文内容能够帮助到你&#xff01;&#xff01; 目录 零&#xff1a;HTML开发工具VSCode的使用 1&#xff1a;创建项目 2&#xff1a;创建格式模板&#x…

区块链的安全性与透明性:Web3如何重塑信任机制

在数字化时代的浪潮中&#xff0c;信任机制的建立显得尤为重要。随着Web3的崛起&#xff0c;区块链技术以其独特的安全性与透明性&#xff0c;正在重塑我们对信任的理解。区块链不仅为去中心化的互联网架构提供了基础&#xff0c;还通过加密技术和分布式账本&#xff0c;实现了…

[OS] Assignment 3-VM

虚拟机设置 虚拟机登录与使用说明 因为项目3基于 xv6 系统运行&#xff0c;它需要一系列支持工具链。我们已经为您准备好了所有必要的环境。 我们提供了 CSC3150_a3_xv6.ova 文件供 x64 架构 用户使用&#xff08;可以导入到 VirtualBox 或 VMware 中&#xff09;&#xff0…

Redis 位图实现签到之长时间未签到预警

#目前通行系统项目中有一个新需求【通过对通行记录数据定时分析&#xff0c;查询出长时间没 有刷卡/刷脸通行的学生】 #一看到通行签到相关&#xff0c;就想到了redis的位图&#xff0c;理由也有很多帖子说明了&#xff0c;最大优点占用空间小。 一.redis命令行 SETBIT&#…

java 多态

1.认识多态 class animals{String name"animals";public void run(){} } class cat extends animals{String name"cat";Overridepublic void run(){System.out.println("cat run");} } class dog extends animals{String name"dog";Ov…

Android TextView自动换行文本显示不全解决

某些情况下&#xff0c;TextView自动换行后&#xff0c;会出现每行结尾处显示不全的问题&#xff0c; 如图&#xff1a; 常见解决方案&#xff1a; 设置TextView的“ellipsize”属性为“end” 实测无效&#xff01;将TextView外部的Layout改为RelativeLayout 实测无效&…

基于springboot+vue实现的养老院管理系统(源码+L文+ppt)

基于springbootvue实现的养老院管理系统&#xff08;源码L文ppt&#xff09;4-106 养老院系统管理是一个综合性养老在线平台&#xff0c;旨在综合并简化养老机构中的照护流程。该系统集成了多种功能&#xff0c;以支持医生、护士、家属及管理员等不同角色的需求。对于医务人员而…