数据结构(超详细讲解!!)第十八节 串(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算法 算法在字符比较不相等,需要回溯(即ii-j1):即退到s中的下一个字符开始进行继续匹配。 最好情况下的时间复杂度为O(m)。 最坏情况下的时间复杂度为O(nm)。 平均的时间复杂度为O(nm)。 2.KMP算法 KMP算法是D.E.Knuth、…...
软考_软件设计师
算法: 1、直接插入排序 详解: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资源异常时,系统产生此告警。 当Manager中的Ldap资源恢复,且告警处理完成时,告警恢复。 告警属性 告警参数 对系统的影响 Ldap资源异常,Manager和组件WebUI认证服务不可用,无法对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如何导出接口的几种方法,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下 前言: 我的文章还是一贯的作风,简确用风格(简单确实有用)&…...
Java进阶(Set)——面试时Set常见问题解读 结合源码分析
前言 List、Set、HashMap作为Java中常用的集合,需要深入认识其原理和特性。 本篇博客介绍常见的关于Java中Set集合的面试问题,结合源码分析题目背后的知识点。 关于List的博客文章如下: Java进阶(List)——面试时L…...
【强化学习】12 —— 策略梯度(REINFORCE )
文章目录 前言策略梯度基于策略的强化学习的优缺点Example:Aliased Gridworld策略目标函数策略优化策略梯度利用有限差分计算策略梯度得分函数和似然比策略梯度定理蒙特卡洛策略梯度(Monte-Carlo Policy Gradient)Puck World Example Softmax随机策略 代…...
Kubernetes Taint(污点) 和 Toleration(容忍)
Author:rab 目录 前言一、Taint(污点)1.1 概述1.2 查看节点 Taint1.3 标记节点 Taint1.4 删除节点 Taint 二、Toleration(容忍) 前言 Kubernetes 中的污点(Taint)和容忍(Toleration…...
使用cv::FileStorage时出错 Can‘t open file: yaml‘ in read mode
1. 使用说明 在做的一个c工程项目,想加一个配置文件,我发现主要有两种主流的方式, (1)opencv有cv::FileStorage这样的一个函数可以使用。 (2)也可以使用cpp-yaml GitHub - jbeder/yaml-cpp: …...
代码之困:那些让你苦笑不得的bug
在编写代码的过程中,我们常常会遇到各种各样的bug。有的时候,我们花费了大量的时间和精力去寻找问题的根源,但却找不到任何线索。然而,令人哭笑不得的是,有时候这些问题的解决方案却是如此简单,以至于我们不…...
【C语言初学者周冲刺计划】2.2用选择法对10个整数从小到大排序
目录 1解题思路: 2代码如下: 3运行结果: 4总结: 1解题思路: 首先利用一维数组和循环语句输入10个整数,然后利用双循环的嵌套进行比较大小,最后输出结果; 2代码如下: #include&…...
c++系列——智能指针
1.智能指针的使用及原理 1.1 RAII RAII(Resource Acquisition Is Initialization)是一种利用对象生命周期来控制程序资源(如内 存、文件句柄、网络连接、互斥量等等)的简单技术。 在对象构造时获取资源,接着控制对资…...
力扣日记10.30-【栈与队列篇】滑动窗口最大值
力扣日记:【栈与队列篇】滑动窗口最大值 日期:2023.10.30 参考:代码随想录、力扣 239. 滑动窗口最大值 题目描述 难度:困难 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只…...
docker与宿主机共享内存通信
docker与宿主机共享内存通信 docker中的进程要与宿主机使用共享内存通信,需要在启动容器的时候指定“–ipchost”选项。然后再编写相应的共享内存的程序,一个跑在宿主机上,另一个跑在docker上面。 宿主机程序准备 shm_data.h #ifndef _SH…...
A股风格因子看板 (2023.10 第13期)
该因子看板跟踪A股风格因子,该因子主要解释沪深两市的市场收益、刻画市场风格趋势的系列风格因子,用以分析市场风格切换、组合风格暴露等。 今日为该因子跟踪第13期,指数组合数据截止日2023-09-30,要点如下 近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、输入输出 二、算法分析...
期中考成绩一键私发
作为一名教师,期中考试后最繁忙的事情之一就是发布成绩。每个学生都希望尽快知道自己的成绩,而作为老师,我们需要一种更高效、更方便的方式来完成这项任务。今天,我就来给大家介绍一种成绩查询系统,让我们一起告别繁琐…...
idea中Run/Debug Python项目报错 Argument for @NotNull parameter ‘module‘ of ...
idea中Run/Debug Python项目报错 Argument for NotNull parameter module of ... idea中运行Python项目main.py时报错: Error running main: Argument for NotNull parameter module of com/intellij/openapi/roots/ModuleRootManager.getInstance must not be nu…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
作为测试我们应该关注redis哪些方面
1、功能测试 数据结构操作:验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化:测试aof和aof持久化机制,确保数据在开启后正确恢复。 事务:检查事务的原子性和回滚机制。 发布订阅:确保消息正确传递。 2、性…...
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要
根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分: 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...
k8s从入门到放弃之Pod的容器探针检测
k8s从入门到放弃之Pod的容器探针检测 在Kubernetes(简称K8s)中,容器探测是指kubelet对容器执行定期诊断的过程,以确保容器中的应用程序处于预期的状态。这些探测是保障应用健康和高可用性的重要机制。Kubernetes提供了两种种类型…...
7种分类数据编码技术详解:从原理到实战
在数据分析和机器学习领域,分类数据(Categorical Data)的处理是一个基础但至关重要的环节。分类数据指的是由有限数量的离散值组成的数据类型,如性别(男/女)、颜色(红/绿/蓝)或产品类…...
开源 vGPU 方案:HAMi,实现细粒度 GPU 切分
本文主要分享一个开源的 GPU 虚拟化方案:HAMi,包括如何安装、配置以及使用。 相比于上一篇分享的 TimeSlicing 方案,HAMi 除了 GPU 共享之外还可以实现 GPU core、memory 得限制,保证共享同一 GPU 的各个 Pod 都能拿到足够的资源。…...
