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

数据结构(超详细讲解!!)第十八节 串(KMP算法)

1.BF算法

算法在字符比较不相等,需要回溯(即i=i-j+1):即退到s中的下一个字符开始进行继续匹配。

最好情况下的时间复杂度为O(m)。

最坏情况下的时间复杂度为O(n×m)。

平均的时间复杂度为O(n×m)。

2.KMP算法

KMP算法是D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的,简称KMP算法。        

该算法较BF算法有较大改进,主要是消除了主串指针的回溯,从而使算法效率有了某种程度的提高。

设串s的长度为n,串t长度为m。        

在KMP算法中求next数组的时间复杂度为O(m),在后面的匹配中因主串s的下标不减即不回溯,比较次数可记为n,所以KMP算法平均时间复杂度为O(n+m)。        

最坏的时间复杂度为O(n × m)。

int KMPIndex(SqString s,SqString t) 
{     int next[MaxSize], i=0, j=0;GetNext(t,next);while (i<s.length && j<t.length) {  if (j==-1 || s.data[i]==t.data[j]) {    i++;j++;			//i、j各增1}else   j=next[j]; 		//i不变,j后退}if (j>=t.length)return(i-t.length);		//返回匹配模式串的首字符下标elsereturn(-1);		/

由模式串t求next值的算法:

void GetNext(SString t,int next[])	 
{     int j, k;j=0;  k=-1;  next[0]=-1;while (j<t.length-1){	if (k==-1 || t.data[j]==t.data[k]){      j++; k++;next[j]=k;}else  k=next[k];}
}

相关文章:

数据结构(超详细讲解!!)第十八节 串(KMP算法)

1.BF算法 算法在字符比较不相等&#xff0c;需要回溯&#xff08;即ii-j1&#xff09;&#xff1a;即退到s中的下一个字符开始进行继续匹配。 最好情况下的时间复杂度为O(m)。 最坏情况下的时间复杂度为O(nm)。 平均的时间复杂度为O(nm)。 2.KMP算法 KMP算法是D.E.Knuth、…...

软考_软件设计师

算法&#xff1a; 1、直接插入排序 详解&#xff1a;https://blog.csdn.net/qq_44616044/article/details/115708056 void insertSort(int data[],int n){int i,j,temp;for(i1;i<n;i){if(data[i]<data[i-1]){temp data[i];data[i] data[i-1];for(ji-1;j>0&&am…...

大数据之LibrA数据库系统告警处理(ALM-12004 OLdap资源异常)

告警解释 当Manager中的Ldap资源异常时&#xff0c;系统产生此告警。 当Manager中的Ldap资源恢复&#xff0c;且告警处理完成时&#xff0c;告警恢复。 告警属性 告警参数 对系统的影响 Ldap资源异常&#xff0c;Manager和组件WebUI认证服务不可用&#xff0c;无法对Web上层…...

详解—数据结构《树和二叉树》

目录 一.树概念及结构 1.1树的概念 1.2树的表示 二.二叉树的概念及结构 2.1概念 2.2二叉树的特点 2.3现实中的二叉树 2.4数据结构中的二叉树 2.5 特殊的二叉树 2.6二叉树的存储结构 2.6.1二叉树的性质 2.6.2 顺序结构 2.6.3链式存储 三. 二叉树的链式结构的遍历 …...

菜单管理中icon图标回显

<el-table-column prop"icon" label"图标" show-overflow-tooltip algin"center"><template v-slot"{ row }"><el-icon :class"row.icon"></el-icon></template></el-table-column>...

Postman如何导出接口的几种方法

本文主要介绍了Postman如何导出接口的几种方法&#xff0c;文中通过示例代码介绍的非常详细&#xff0c;具有一定的参考价值&#xff0c;感兴趣的小伙伴们可以参考一下 前言&#xff1a; 我的文章还是一贯的作风&#xff0c;简确用风格&#xff08;简单确实有用&#xff09;&…...

Java进阶(Set)——面试时Set常见问题解读 结合源码分析

前言 List、Set、HashMap作为Java中常用的集合&#xff0c;需要深入认识其原理和特性。 本篇博客介绍常见的关于Java中Set集合的面试问题&#xff0c;结合源码分析题目背后的知识点。 关于List的博客文章如下&#xff1a; Java进阶&#xff08;List&#xff09;——面试时L…...

【强化学习】12 —— 策略梯度(REINFORCE )

文章目录 前言策略梯度基于策略的强化学习的优缺点Example:Aliased Gridworld策略目标函数策略优化策略梯度利用有限差分计算策略梯度得分函数和似然比策略梯度定理蒙特卡洛策略梯度&#xff08;Monte-Carlo Policy Gradient&#xff09;Puck World Example Softmax随机策略 代…...

Kubernetes Taint(污点) 和 Toleration(容忍)

Author&#xff1a;rab 目录 前言一、Taint&#xff08;污点&#xff09;1.1 概述1.2 查看节点 Taint1.3 标记节点 Taint1.4 删除节点 Taint 二、Toleration&#xff08;容忍&#xff09; 前言 Kubernetes 中的污点&#xff08;Taint&#xff09;和容忍&#xff08;Toleration…...

使用cv::FileStorage时出错 Can‘t open file: yaml‘ in read mode

1. 使用说明 在做的一个c工程项目&#xff0c;想加一个配置文件&#xff0c;我发现主要有两种主流的方式&#xff0c; &#xff08;1&#xff09;opencv有cv::FileStorage这样的一个函数可以使用。 &#xff08;2&#xff09;也可以使用cpp-yaml GitHub - jbeder/yaml-cpp: …...

代码之困:那些让你苦笑不得的bug

在编写代码的过程中&#xff0c;我们常常会遇到各种各样的bug。有的时候&#xff0c;我们花费了大量的时间和精力去寻找问题的根源&#xff0c;但却找不到任何线索。然而&#xff0c;令人哭笑不得的是&#xff0c;有时候这些问题的解决方案却是如此简单&#xff0c;以至于我们不…...

【C语言初学者周冲刺计划】2.2用选择法对10个整数从小到大排序

目录 1解题思路&#xff1a; 2代码如下&#xff1a; 3运行结果: 4总结&#xff1a; 1解题思路&#xff1a; 首先利用一维数组和循环语句输入10个整数&#xff0c;然后利用双循环的嵌套进行比较大小&#xff0c;最后输出结果&#xff1b; 2代码如下&#xff1a; #include&…...

c++系列——智能指针

1.智能指针的使用及原理 1.1 RAII RAII&#xff08;Resource Acquisition Is Initialization&#xff09;是一种利用对象生命周期来控制程序资源&#xff08;如内 存、文件句柄、网络连接、互斥量等等&#xff09;的简单技术。 在对象构造时获取资源&#xff0c;接着控制对资…...

力扣日记10.30-【栈与队列篇】滑动窗口最大值

力扣日记&#xff1a;【栈与队列篇】滑动窗口最大值 日期&#xff1a;2023.10.30 参考&#xff1a;代码随想录、力扣 239. 滑动窗口最大值 题目描述 难度&#xff1a;困难 给你一个整数数组 nums&#xff0c;有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只…...

docker与宿主机共享内存通信

docker与宿主机共享内存通信 docker中的进程要与宿主机使用共享内存通信&#xff0c;需要在启动容器的时候指定“–ipchost”选项。然后再编写相应的共享内存的程序&#xff0c;一个跑在宿主机上&#xff0c;另一个跑在docker上面。 宿主机程序准备 shm_data.h #ifndef _SH…...

A股风格因子看板 (2023.10 第13期)

该因子看板跟踪A股风格因子&#xff0c;该因子主要解释沪深两市的市场收益、刻画市场风格趋势的系列风格因子&#xff0c;用以分析市场风格切换、组合风格暴露等。 今日为该因子跟踪第13期&#xff0c;指数组合数据截止日2023-09-30&#xff0c;要点如下 近1年A股风格因子检验统…...

ORB-SLAM3算法2之EuRoc、TUM和KITTI开源数据集运行ORB-SLAM3生成轨迹并用evo工具评估轨迹

文章目录 0 引言1 数据和真值1.1 TUM1.2 EuRoc1.3 KITTI2 ORB-SLAM3的EuRoc示例2.1 纯单目的示例2.2 纯单目的轨迹评估2.3 纯双目的示例2.4 纯双目的轨迹评估2.5 单目和IMU的示例2.6 单目和IMU的轨迹评估2.7 双目和IMU的示例2.8 双目和IMU的轨迹评估2.9 前四种的评估结果对比3 …...

【蓝桥杯选拔赛真题07】C++小球自由落体 青少年组蓝桥杯C++选拔赛真题 STEMA比赛真题解析

目录 C/C++小球自由落体 一、题目要求 1、编程实现 2、输入输出 二、算法分析...

期中考成绩一键私发

作为一名教师&#xff0c;期中考试后最繁忙的事情之一就是发布成绩。每个学生都希望尽快知道自己的成绩&#xff0c;而作为老师&#xff0c;我们需要一种更高效、更方便的方式来完成这项任务。今天&#xff0c;我就来给大家介绍一种成绩查询系统&#xff0c;让我们一起告别繁琐…...

idea中Run/Debug Python项目报错 Argument for @NotNull parameter ‘module‘ of ...

idea中Run/Debug Python项目报错 Argument for NotNull parameter module of ... idea中运行Python项目main.py时报错&#xff1a; Error running main: Argument for NotNull parameter module of com/intellij/openapi/roots/ModuleRootManager.getInstance must not be nu…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...