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 位置 a和 15 -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,str1是否包含str2,如果包含返回str2在str1中开始的位置。并做到时间复杂度为 O ( n ) O(n) O(n) 2 前缀问题 求一个字符串中每个字符前缀和后缀相…...
[matconvnet]matconvnet-1.0-beta-25在cuda11.1以上编译问题总结
首先可以肯定是matconvnet-1.0-beta-25不支持cuda11.1及其以上版本,因为cudnn版本问题导致源码api接口不一样,会下面类似报错 E:\Matlab\R2020a\matconvnet-1.0-beta25\matlab\src\bits\datacu.hpp(89): error: identifier "cudnnConvolutionFwdPr…...
自动化驱动程序管理
在部署操作系统时,每次都从下载和分发所需的驱动程序中实现真正的独立性可能是一场艰苦的战斗。特别是具有硬件多样化的环境,并且需要支持新的硬件类型时。借助 OS Deployer,可以对所有端点使用一个映像,无论品牌和型号如何&#…...
智能合约编写高级篇(二)区块哈希介绍
本文档从区块哈希基本概念出发,详细介绍了中移链的区块哈希交易接口和应用方向。适用于EOS区块链智能合约高级开发人员,熟悉如何获取当前发生交易所在的区块号和区块哈希前缀,并通过Tapos机制验证交易的有效性。 01 概述 (一&…...
二进制链表转整数
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。 请你返回该链表所表示数字的 十进制值 。 示例 1: 输入:head [1,0,1] 输出:5 解释:二进制数 (101) 转化为十进…...
Python爬虫进阶:使用Scrapy库进行数据提取和处理
在我们的初级教程中,我们介绍了如何使用Scrapy创建和运行一个简单的爬虫。在这篇文章中,我们将深入了解Scrapy的强大功能,学习如何使用Scrapy提取和处理数据。 一、数据提取:Selectors和Item 在Scrapy中,提取数据主要…...
五)Stable Diffussion使用教程:文生图之高清修复
上一篇我们说到图生图,这一篇来说说高清修复。 上一篇我们通过一个例子实现了图生图的功能,使用一张图片生成了另一种风格的图片。 然而,我们生成的图片质量不尽如人意。 虽然我们之前也提到设置分辨率、精炼提示词去提升画面质量等等,但是实际用下来发现,分辨率拉得太…...
SQL SERVER 如何实现UNDO REDO 和PostgreSQL 有近亲关系吗
开头还是介绍一下群,如果感兴趣PolarDB ,MongoDB ,MySQL ,PostgreSQL ,SQL Server,Redis ,Oracle ,Oceanbase 等有问题,有需求都可以加群群内有各大数据库行业大咖,CTO,可以解决你的问题。加群请加微信号 l…...
SpringBoot原理-自动配置-原理分析-源码跟踪
自动配置原理 SpringBootApplication 该注解标识在SpringBoot项目的启动类上,是SpringBoot中最为重要的注解,该注解由三个部分组成。 SpringBootConfiguration:该注解与Configuration注解作用一样,用来声明当前类为一个配置类Comp…...
安全基础 --- 原型链污染
原型链 大部分面向对象的编程语言,都是通过“类”(class)实现对象的继承。传统上,JavaScript 语言的继承不通过 class,而是通过“原型对象”(prototype)实现 1、prototype 属性的作用 JavaScri…...
c++中的常用知识点总结
命名空间 使用命名空间之后,调用代码时可以省去也可以不省去相关的前缀。 #include <iostream>using namespace std;//使用c自己的命名空间 int main() {int num1 10;std::cout << "Hello, World!" << std::endl;cout<<num1&l…...
Leetcode:349. 两个数组的交集【题解超详细】
题目 给定两个数组 nums1 和 nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 难度:简单 题目链接:349.两个数组的交集 示例 1: 输入:nums1 [1,2,2,1], nums2 [2,…...
Java 【异常】
一、认识异常 Exception 在 Java 中,将程序执行过程中发生的不正常行为称为异常 。 异常是异常exception,报错是报错error 1.算数异常 0不能作为除数,所以算数异常 2.空指针异常 arr不指向任何对象,打印不出arr的长度,…...
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 开发中,一个重要的组成部分便是数据库了。Web 程序中最常用的莫过于关系型数据库了,也称 SQL 数据库。另外,文档数据库(如 mongodb)、键值对数据库(如 redis)近几年也逐渐在 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))
装饰器模式 装饰器模式是一种结构型设计模式,用于动态地给对象添加额外的行为或责任,而不需要改变原始对象的结构。通过创建一个包装器类(装饰器),它包含原始对象的引用,并提供与原始对象相同的接口&#…...
小程序v-for与key值使用
小程序中的v-for和key与Vue中的用法基本相同。v-for用于循环渲染列表,key用于给每个循环项分配一个唯一的标识。 使用v-for时,通常建议使用wx:for代替,例如: <view wx:for"{{ items }}" wx:key"id">{…...
Qt包含文件不存在问题解决 QNetworkAccessManager
这里用到了Qt的网络模块,在.pro中添加了 QT network 但是添加 #include <QNetworkAccessManager> 会报错说找不到,可以通过在项目上右键执行qmake后,直接#include <QNetworkAccessManager>就不会报错了:...
Python爬虫实战:研究MechanicalSoup库相关技术
一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
虚拟电厂发展三大趋势:市场化、技术主导、车网互联
市场化:从政策驱动到多元盈利 政策全面赋能 2025年4月,国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》,首次明确虚拟电厂为“独立市场主体”,提出硬性目标:2027年全国调节能力≥2000万千瓦࿰…...
