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

KMP 算法详解

KMP算法详解

  • 1 KMP算法解决的问题
  • 2 前缀问题
  • 3 KMP 算法

 

1 KMP算法解决的问题

字符串str1和str2,str1是否包含str2,如果包含返回str2在str1中开始的位置。并做到时间复杂度为 O ( n ) O(n) O(n)


 

2 前缀问题

求一个字符串中每个字符前缀和后缀相等的最大长度
比如求字符串 :
a b b a a b b a b b a a b b a k l

假设此时来到的位置为 i

求解方法如下:
先看i - 1 位置的 前缀和后缀相等的最大长度 CN ;

比较 CN 位置和 i - 1位置的字符串是否相等,如果相等,则i位置的前缀和后缀相等的最大长度为 CN + 1;

如果不相等,得到 CN位置的前缀和后缀相等的最大长度CN,继续用CN位置的字符和 i - 1位置的字符比较

循环上述过程,碰到CN为0,则i位置的 前缀和后缀相等的最大长度为0

比如求字符串
a b b a a b b a b b a a b b c k l k字符的前缀和后缀相等的最大长度过程如下 :
k所在的位置 15,前一个位置的字符为 c 字符c 前缀和后缀相等的最大长度cn 为7,
则比较字符串中 7 位置 a15 -1 位置的字符 a 相等,则直接返回 8

获取一个字符串中所有字符前缀和后缀相等的最大长度代码实现

coding

/**** @param m 获取字符数组m每一个位置 前缀和后缀相等的最大长度* @return*/public static int[] getNextArr(char[] m){if (m.length == 1){return new int[]{-1};}int[] retArr = new int[m.length];// 规定 0 位置 前缀和后缀相等的最大长度为 -1// 规定 1 位置 前缀和后缀相等的最大长度为 0retArr[0] = -1;retArr[1] = 0;// 使用字符数组中那个位置的字符与 i - 1 位置的字符进行比较int cmpIndex = 0; // i - 1位置的字符前缀和后缀相等的最大长度// i在2位置时,使用i - 1位置的,即 1位置的字符前缀和后缀相等的最大长度// 初始时,使用 0 位置的字符和1位置的字符比较int i = 2;while (i < m.length){// cmpIndex位置字符和i位置的字符相等 // 则i位置的前缀和后缀相等的最大长度为cmpIndex+1if (m[cmpIndex] == m[i - 1]){retArr[i++] = ++cmpIndex;} else if (cmpIndex > 0){cmpIndex = retArr[cmpIndex];} else {retArr[i++] = 0;}}return retArr;}

3 KMP 算法

coding

/*** KMP算法解决的问题* 字符串str1和str2,str1是否包含str2,如果包含返回str2在str1中开始的位置。* 如何做到时间复杂度O(N)完成?* 字符串1的长度是M* 字符串的长度是N* 暴力匹配的时间复杂度O(M * N)* 前缀和后缀相等的最大长度* 前缀和后缀不能取到整体**/public static int getIndex(String s1,String s2){if (s1 == null || s2 == null || s2.length() < 1 || s2.length() > s1.length()){return -1;}char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int[] nextArr = getNextArr(str2);int i1 = 0;int i2 = 0;while (i1 < str1.length && i2 < str2.length){if (str1[i1] == str2[i2]){i1++;i2++;} else if (nextArr[i2] == -1){//第一个字符i1 ++;} else {// i2直接到 i2位置前缀和后缀相等最大长度的位置i2 = nextArr[i2];}}// 只有 i1 == str2.length时才匹配成功 否则str2就不在str1中return i2 == str2.length ? i1 - i2 : -1;}

相关文章:

KMP 算法详解

KMP算法详解 1 KMP算法解决的问题 2 前缀问题 3 KMP 算法 1 KMP算法解决的问题 字符串str1和str2&#xff0c;str1是否包含str2&#xff0c;如果包含返回str2在str1中开始的位置。并做到时间复杂度为 O ( n ) O(n) O(n) 2 前缀问题 求一个字符串中每个字符前缀和后缀相…...

[matconvnet]matconvnet-1.0-beta-25在cuda11.1以上编译问题总结

首先可以肯定是matconvnet-1.0-beta-25不支持cuda11.1及其以上版本&#xff0c;因为cudnn版本问题导致源码api接口不一样&#xff0c;会下面类似报错 E:\Matlab\R2020a\matconvnet-1.0-beta25\matlab\src\bits\datacu.hpp(89): error: identifier "cudnnConvolutionFwdPr…...

自动化驱动程序管理

在部署操作系统时&#xff0c;每次都从下载和分发所需的驱动程序中实现真正的独立性可能是一场艰苦的战斗。特别是具有硬件多样化的环境&#xff0c;并且需要支持新的硬件类型时。借助 OS Deployer&#xff0c;可以对所有端点使用一个映像&#xff0c;无论品牌和型号如何&#…...

智能合约编写高级篇(二)区块哈希介绍

本文档从区块哈希基本概念出发&#xff0c;详细介绍了中移链的区块哈希交易接口和应用方向。适用于EOS区块链智能合约高级开发人员&#xff0c;熟悉如何获取当前发生交易所在的区块号和区块哈希前缀&#xff0c;并通过Tapos机制验证交易的有效性。 01 概述 &#xff08;一&…...

二进制链表转整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 示例 1&#xff1a; 输入&#xff1a;head [1,0,1] 输出&#xff1a;5 解释&#xff1a;二进制数 (101) 转化为十进…...

Python爬虫进阶:使用Scrapy库进行数据提取和处理

在我们的初级教程中&#xff0c;我们介绍了如何使用Scrapy创建和运行一个简单的爬虫。在这篇文章中&#xff0c;我们将深入了解Scrapy的强大功能&#xff0c;学习如何使用Scrapy提取和处理数据。 一、数据提取&#xff1a;Selectors和Item 在Scrapy中&#xff0c;提取数据主要…...

五)Stable Diffussion使用教程:文生图之高清修复

上一篇我们说到图生图,这一篇来说说高清修复。 上一篇我们通过一个例子实现了图生图的功能,使用一张图片生成了另一种风格的图片。 然而,我们生成的图片质量不尽如人意。 虽然我们之前也提到设置分辨率、精炼提示词去提升画面质量等等,但是实际用下来发现,分辨率拉得太…...

SQL SERVER 如何实现UNDO REDO 和PostgreSQL 有近亲关系吗

开头还是介绍一下群&#xff0c;如果感兴趣PolarDB ,MongoDB ,MySQL ,PostgreSQL ,SQL Server&#xff0c;Redis &#xff0c;Oracle ,Oceanbase 等有问题&#xff0c;有需求都可以加群群内有各大数据库行业大咖&#xff0c;CTO&#xff0c;可以解决你的问题。加群请加微信号 l…...

SpringBoot原理-自动配置-原理分析-源码跟踪

自动配置原理 SpringBootApplication 该注解标识在SpringBoot项目的启动类上&#xff0c;是SpringBoot中最为重要的注解&#xff0c;该注解由三个部分组成。 SpringBootConfiguration&#xff1a;该注解与Configuration注解作用一样&#xff0c;用来声明当前类为一个配置类Comp…...

安全基础 --- 原型链污染

原型链 大部分面向对象的编程语言&#xff0c;都是通过“类”&#xff08;class&#xff09;实现对象的继承。传统上&#xff0c;JavaScript 语言的继承不通过 class&#xff0c;而是通过“原型对象”&#xff08;prototype&#xff09;实现 1、prototype 属性的作用 JavaScri…...

c++中的常用知识点总结

命名空间 使用命名空间之后&#xff0c;调用代码时可以省去也可以不省去相关的前缀。 #include <iostream>using namespace std;//使用c自己的命名空间 int main() {int num1 10;std::cout << "Hello, World!" << std::endl;cout<<num1&l…...

Leetcode:349. 两个数组的交集【题解超详细】

题目 给定两个数组 nums1 和 nums2 &#xff0c;返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 难度&#xff1a;简单 题目链接&#xff1a;349.两个数组的交集 示例 1&#xff1a; 输入&#xff1a;nums1 [1,2,2,1], nums2 [2,…...

Java 【异常】

一、认识异常 Exception 在 Java 中&#xff0c;将程序执行过程中发生的不正常行为称为异常 。 异常是异常exception&#xff0c;报错是报错error 1.算数异常 0不能作为除数&#xff0c;所以算数异常 2.空指针异常 arr不指向任何对象&#xff0c;打印不出arr的长度&#xff0c;…...

B - Polycarp‘s Practice

Polycarp is practicing his problem solving skill. He has a list of nn problems with difficulties a_1, a_2, \dots, a_na1​,a2​,…,an​, respectively. His plan is to practice for exactly kk days. Each day he has to solve at least one problem from his list. …...

朴素贝叶斯数据分类------

------------------后期会编辑些关于朴素贝叶斯算法的推导及代码分析----------------- import numpy as np import pandas as pd from sklearn.model_selection import train_test_split from sklearn.naive_bayes import GaussianNB, BernoulliNB, MultinomialNB from sklear…...

flask中的操作数据库的插件Flask-SQLAlchemy

1、ORM 框架 Web 开发中&#xff0c;一个重要的组成部分便是数据库了。Web 程序中最常用的莫过于关系型数据库了&#xff0c;也称 SQL 数据库。另外&#xff0c;文档数据库&#xff08;如 mongodb&#xff09;、键值对数据库&#xff08;如 redis&#xff09;近几年也逐渐在 w…...

arrow的使用

pandas2.0引入了pyarrow作为可选后端,比numpy的性能提高很多,所以为了改造backtrader,用cython和c++重写整个框架,准备用arrow作为底层的数据结构(backtrader现在的底层数据结构是基于python array构建的) 安装arrow推荐使用vcpkg git clone https://github.com/Microsoft…...

【24种设计模式】装饰器模式(Decorator Pattern(Wrapper))

装饰器模式 装饰器模式是一种结构型设计模式&#xff0c;用于动态地给对象添加额外的行为或责任&#xff0c;而不需要改变原始对象的结构。通过创建一个包装器类&#xff08;装饰器&#xff09;&#xff0c;它包含原始对象的引用&#xff0c;并提供与原始对象相同的接口&#…...

小程序v-for与key值使用

小程序中的v-for和key与Vue中的用法基本相同。v-for用于循环渲染列表&#xff0c;key用于给每个循环项分配一个唯一的标识。 使用v-for时&#xff0c;通常建议使用wx:for代替&#xff0c;例如&#xff1a; <view wx:for"{{ items }}" wx:key"id">{…...

Qt包含文件不存在问题解决 QNetworkAccessManager

这里用到了Qt的网络模块&#xff0c;在.pro中添加了 QT network 但是添加 #include <QNetworkAccessManager> 会报错说找不到&#xff0c;可以通过在项目上右键执行qmake后&#xff0c;直接#include <QNetworkAccessManager>就不会报错了&#xff1a;...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

微信小程序云开发平台MySQL的连接方式

注&#xff1a;微信小程序云开发平台指的是腾讯云开发 先给结论&#xff1a;微信小程序云开发平台的MySQL&#xff0c;无法通过获取数据库连接信息的方式进行连接&#xff0c;连接只能通过云开发的SDK连接&#xff0c;具体要参考官方文档&#xff1a; 为什么&#xff1f; 因为…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

【网络安全】开源系统getshell漏洞挖掘

审计过程&#xff1a; 在入口文件admin/index.php中&#xff1a; 用户可以通过m,c,a等参数控制加载的文件和方法&#xff0c;在app/system/entrance.php中存在重点代码&#xff1a; 当M_TYPE system并且M_MODULE include时&#xff0c;会设置常量PATH_OWN_FILE为PATH_APP.M_T…...

永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器

一、原理介绍 传统滑模观测器采用如下结构&#xff1a; 传统SMO中LPF会带来相位延迟和幅值衰减&#xff0c;并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF)&#xff0c;可以去除高次谐波&#xff0c;并且不用相位补偿就可以获得一个误差较小的转子位…...

Linux安全加固:从攻防视角构建系统免疫

Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

作为点的对象CenterNet论文阅读

摘要 检测器将图像中的物体表示为轴对齐的边界框。大多数成功的目标检测方法都会枚举几乎完整的潜在目标位置列表&#xff0c;并对每一个位置进行分类。这种做法既浪费又低效&#xff0c;并且需要额外的后处理。在本文中&#xff0c;我们采取了不同的方法。我们将物体建模为单…...