当前位置: 首页 > 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;...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...