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>就不会报错了:...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
遍历 Map 类型集合的方法汇总
1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
【生成模型】视频生成论文调研
工作清单 上游应用方向:控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...
安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)
船舶制造装配管理现状:装配工作依赖人工经验,装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书,但在实际执行中,工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
