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

数据结构与算法系列之kmp算法

在这里插入图片描述

什么是kmp算法

1.kmp算法是一种改进的字符串算法,其核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数已达到快速匹配的目的。
它主要实现作用的是 在 (主串)中找到 (匹配)字符串

在这里插入图片描述

BF算法与kmp算法的差别

bf算法如下所示 从首元素字符开始依次比较 ,如果相同则比较下一位元素,如果匹配失败 ,匹配字符串从头开始 ,主串从第二个字符开始比较,直到主字符串全部匹配完。如果匹配成功返回主字符串中第一次出现匹配字符串的位置。

在这里插入图片描述
在这里插入图片描述

kmp算法如下所示,kmp与bf不一样的地方在于:主串的所指向的字符不会后退,匹配串中所指向的也不会移动到首字符位置

在这里插入图片描述

在这里插入图片描述

kmp的回退规则,next数组的介绍

目的是使 指向主串字符不会回退 ,匹配串回退到一个特定位置
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

这就是next数组的来源
规定next[0]=-1 next[1]=0
在这里插入图片描述

回退前提 : p[i] == p[k] 则 p[i] == p[k] next[i+1] == k+1 ,如果 p[i] != p[k] 则 next[k] != k, k==next[k] ,一直回退直到p[i] == p[k]

p[i] == p[k] 如下
在这里插入图片描述
p[i] != p[k]如下

在这里插入图片描述

kmp算法代码实现(C语言版)

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>
void GetNext(char*sub, int* next ,int LenSub)
{next[0] = -1;next[1] = 0;int k = 0;int i = 2;while(i < LenSub){if (k == -1 || sub[i - 1] == sub[k]){next[i] = k + 1;i++;k++;}else{k = next[k];}}
}
int KMP(char* str, char* sub, int pos)
{assert(str  && sub );int LenStr = strlen(str);int LenSub = strlen(sub);if (LenStr == 0 || LenSub == 0)return -1;if (pos < 0 || pos >= LenStr)return -1;int* next = (int*)malloc(sizeof(int) * LenSub);assert(next);GetNext(sub, next,LenSub);int i = pos;//主串int j = 0;//字串while (i < LenStr && j < LenSub){if (j == -1 || str[i] == sub[j]){i++;j++;}else{j = next[j];}}if (j >= LenSub)return i - j;return -1;
}int main()
{printf("%d", KMP("ababcabcdabcde", "abcd", 0));return 0;
}

在这里插入图片描述

相关文章:

数据结构与算法系列之kmp算法

什么是kmp算法 1.kmp算法是一种改进的字符串算法&#xff0c;其核心是利用匹配失败后的信息&#xff0c;尽量减少模式串与主串的匹配次数已达到快速匹配的目的。 它主要实现作用的是 在 &#xff08;主串&#xff09;中找到 &#xff08;匹配&#xff09;字符串。 例 BF算法与k…...

算法分析详解

自古老的公元前1世纪开始&#xff0c;《周髀算经》就作为中国最古老的天文学和数学著作。 《周髀算经》采用最简便可行的方法确定天文历法&#xff0c;揭示日月星辰的运行规律&#xff0c;包括四季更替&#xff0c;气候变化&#xff0c;南北有极&#xff0c;昼夜相推的道理。为…...

东南大学自然辩证法概论期末总结

写在前面 作者&#xff1a;夏日 博客地址&#xff1a;https://blog.csdn.net/zss192 本文为2022年东南大学自然辩证法概论期末总结&#xff0c;内容为根据老师所发题纲综合多个资料总结得来 考试形式&#xff1a;从老师所发题纲&#xff0c;10个题目中选出4个&#xff0c;题…...

《爆肝整理》保姆级系列教程python接口自动化(二十)--token登录(详解)

简介 为了验证用户登录情况以及减轻服务器的压力&#xff0c;减少频繁的查询数据库&#xff0c;使服务器更加健壮。有些登录不是用 cookie 来验证的&#xff0c;是用 token 参数来判断是否登录。token 传参有两种一种是放在请求头里&#xff0c;本质上是跟 cookie 是一样的&…...

k8s种的kubectl命令

一.kubectl基本命令1.1 称述式资源管理的方法kubernetes集群管理集群资源的唯一入口是通过相应的方法调用apiserver的接口kubectl是官方的CLI命令行工具&#xff0c;用于与apiserver进行通信&#xff0c;将用户在命令行输入的命令&#xff0c;组织并转化为apiserver能识别的信息…...

数组(一)-- LeetCode[26][80] 删除有序数组中的重复元素

1 删除有序数组中的重复项 1.1 题目描述 给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次&#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度&#xff0c…...

GEE学习笔记 六十三:新的地图图层ui.Map.CloudStorageLayer

在GEE中导出数据有一种方式是直接导出地图到Google Cloud Storage中&#xff0c;也就是Export.map.toCloudStorage(xxx)&#xff0c;这种方式是将我们计算生成影像导出成为静态瓦片的格式存放在Google Cloud Storage中。我们可以在其他的前端程序比如OpenLayer、Mapbox GL JS等…...

ClickHouse 语法详解

ClickHouse有2类解析器&#xff1a;完整SQL解析器&#xff08;递归式解析器&#xff09;&#xff0c;以及数据格式解析器&#xff08;快速流式解析器&#xff09; 除了 INSERT 查询&#xff0c;其它情况下仅使用完整SQL解析器。 INSERT查询会同时使用2种解析器&#xff1a;INSE…...

手把手教你将微信小程序放到git上

背景 首先&#xff0c;要创建一个自己的git仓库&#xff0c;这里默认大家都能够自己创建了git仓库了。如果不会创建仓库的话&#xff0c;百度一下&#xff0c;很容易就能够创建了&#xff01;&#xff08;后续&#xff0c;如有不知道在哪里&#xff0c;怎么创建仓库的话&#…...

功能测试3年,回顾一路走来的艰辛

不论你是什么时候开始接触测试这个行业的&#xff0c;你首先听说的应该是功能测试。通过一些测试手段来验证开发做出的代码是否符合产品的需求&#xff1f;当然你也有自己对功能测试的理解&#xff0c;但是最近两年感觉功能测试好像不太受欢迎&#xff0c;同时不少同学真的是功…...

作为Linux C/C++程序员必备的工具

Linux系统 可以选择centOS或者ubautu server(不建议选择桌面版本的)。不建议裸机安装&#xff0c;玩坏了就特别麻烦。不建议使用有桌面版本的ubautu&#xff0c;在一定程度有桌面的版本的会消耗性能。 如果经济实力允许&#xff0c;可以购买云服务器。 参考文章: Ubuntu server…...

docker Alpine一个只有5M小而美的Docker镜像

docker Alpine一个只有5M小而美的Docker镜像 参考链接: Alpine 一个只有5M的Docker镜像 http://www.infoq.com/cn/news/2016/01/Alpine-Linux-5M-Docker?utm_sourcetuicool&utm_mediumreferral 使用alpinelinux 构建 golang http 启动了才15mb http://blog.csdn.net/fre…...

Springboot扩展点之InstantiationAwareBeanPostProcessor

Springboot扩展点系列实现方式、工作原理集合&#xff1a;Springboot扩展点之ApplicationContextInitializerSpringboot扩展点之BeanFactoryPostProcessorSpringboot扩展点之BeanDefinitionRegistryPostProcessorSpringboot扩展点之BeanPostProcessorSpringboot扩展点之Instant…...

基于 U-Net 网络的遥感图像语义分割 完整代码+论文

一、研究目的U-Net 是一种由全卷积神经网络启发的对称结构网络&#xff0c;在医疗影像分割领域取得了很好的效果。 此次研究尝试使用 U-Net 网络在对多光谱遥感影像数据集上进行训练&#xff0c;尝试使用卷积神经网络自动分割出建筑&#xff0c;希望能够得到一种自动分割遥感影…...

Codeql 编译Shiro1.2.4爬坑

0x00 前言 这个Codeql一定要编译才能生成Database&#xff0c;是真的比较恼火&#xff0c;很多项目都不一定可以生成&#xff0c;环境就是一个非常大的坑&#xff0c;为了防止以后&#xff0c;所以将shiro1.2.4编译过程进行记录。 0x01 正文 首先是需要下载到shiro1.2.4的源…...

新C++(9):谈谈,翻转那些事儿

"相信羁绊&#xff0c;相信微光&#xff0c;相信一切无常。"一、AVL树翻转那些事儿(1)什么是AVL树&#xff1f;在计算机科学中&#xff0c;AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1&#xff0c;所以它也被称为高度平衡树。…...

Java深克隆的几种方式

目录 1、通过继承Cloneable接口&#xff0c;重写clone方法实现深克隆 2、通过序列化与反序列化的方式实现深克隆 3、第三方工具类实现深克隆&#xff0c;克隆对象需继承Serializable接口 3.1、Apache Commons Lang的SerializationUtils.clone方法 3.2、Gson工具类 3.3、F…...

PointNet++的源码运行

首先&#xff0c;从github上下载源码https://github.com/yanx27/Pointnet_Pointnet2_pytorch也可以从百度网盘下载链接&#xff1a;https://pan.baidu.com/s/1sgTYuqnBVC9p3bib450SOQ 提取码&#xff1a;gujd再下载对应的测试数据分类数据modelnet40_normal_resampled下载&…...

npm 上传自己的包

mkdir demo 创建一个新的文件夹 npm init 初始化项目 生成一个package.json文件 name version description等等touch index.js 创建一个node 可执行脚本新的js 文件 #!/usr/bin/env node // 必须在文件头加如上内容指定运行环境为node console.log(hello cli)在package.json 中…...

【Linux】常用命令大全(二)

目录 4. Linux常用命令 4.1 Linux命令初体验 4.2 文件目录操作命令 4.3 拷贝移动命令 4.4 打包压缩命令 4.5 文本编辑命令 4.6 查找命令 4. Linux常用命令 4.1 Linux命令初体验 4.1.1 常用命令演示 在这一部分中&#xff0c;我们主要介绍几个常用的命令&#xff0c…...

Ubuntu系统下交叉编译openssl

一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机&#xff1a;Ubuntu 20.04.6 LTSHost&#xff1a;ARM32位交叉编译器&#xff1a;arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...

高考志愿填报管理系统---开发介绍

高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发&#xff0c;采用现代化的Web技术&#xff0c;为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## &#x1f4cb; 系统概述 ### &#x1f3af; 系统定…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...