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>就不会报错了:...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序
一、开发准备 环境搭建: 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 项目创建: File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...
