KMP算法(C++)
KMP算法与BF算法不一样的在于,当主串与子串不匹配时,主串不回溯,选择了子串回溯,大大提高了运算效率。
借用了next1【】数组,让子串回溯。get_next函数求next1【】数组,get_next函数的实现难点在于下列几行代码:
while (i < T.length)
{
if (j == 0 || T.ch[i] == T.ch[j])
{
++i, ++j;
next1[i] = j;
}
else
j = next1[j];
}
只要明确两点就容易理解:
1、Tj == Tnext[j],那么next[j+1]的最大值为next[j]+1。
2、Tj != Tnext[j],那么next[j+1]可能的次最大值为next[ next[j] ]+1,以此类推即可求出next[j+1]。
#include<iostream>
#include<string>
using namespace std;
int next1[1000];
typedef struct node
{char ch[251];int length=0;//串当前长度
}SString;
void get_next(SString T)
{int i = 1;//当前串正在匹配字符串位置,也是next数组的索引next1[1] = 0;int j = 0;while (i < T.length){if (j == 0 || T.ch[i] == T.ch[j]){++i;++j;next1[i] = j;}elsej = next1[j];}
}
int Index_KMP(SString S, SString T, int pos)//S主串,T子串,pos从主串pos位置开始匹配
{int i = pos, j = 1;//i为主串下标,j为子串下标while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j])//匹配,往下继续{i++;j++;}elsej=next1[j];}if (j >= T.length) return i - T.length;//返回主串与子串匹配时,主串的第一个下标else return 0;
}
int main()
{SString s;SString t;cout << "输入主串长度:" ;cin >> s.length;cout << endl;cout << "输入子串长度:";cin >> t.length;cout << endl << "输入主串:";for (int i = 1; i <= s.length; i++)//从下标1开始储存{cin >> s.ch[i];}cout << endl << "输入子串:";for (int i = 1; i <= t.length; i++){cin >> t.ch[i];}get_next(t);int a = Index_KMP(s, t, 1);cout <<endl<< a;
}

相关文章:
KMP算法(C++)
KMP算法与BF算法不一样的在于,当主串与子串不匹配时,主串不回溯,选择了子串回溯,大大提高了运算效率。 借用了next1【】数组,让子串回溯。get_next函数求next1【】数组,get_next函数的实现难点在于下列几行…...
C++的异常类型与多级catch匹配
try-catch 的用法: try{// 可能抛出异常的语句 }catch(exceptionType variable){// 处理异常的语句 } 我们还遗留下一个问题,就是 catch 关键字后边的exceptionType variable,这节就来详细分析一下。exceptionType是异常类型,它指明了当前的 catch 可以处理什么类型的异常…...
查询IP地址可得到哪些信息
通过IP地址定位,可以获取一些基本的信息,包括以下内容: 1. 地理位置:你可以确定IP地址所在的地理位置,包括国家、州或省、城市和地理坐标。这通常是通过将IP地址与地理位置数据库进行匹配来实现的。 2. ISPÿ…...
考研算法47天:01背包
问题描述 算法详细步骤 代码随想录 (programmercarl.com) ac代码 #include <iostream> using namespace std; int bag[1001]; int bagMax[1001]; int bagvalue[1001]; int main(){int n,v;cin>>n>>v;for(int i0;i<n;i){cin>>bag[i]>>bagva…...
Docker实战技巧(一):Kubernetes基础操作实战
Kubernetes定位在Saas层,重点解决了微服务大规模部署时的服务编排问题 1、关闭防火墙并设置开机禁用 systemctl stop firewalld systemctl disable firewalld 2、配置repo cd /etc/yum.repos.d/ 下载Docker repo wget https://mirrors.aliyun.com/docker-…...
android java读写yaml文件
目录 申请读写权限: build.gradle中添加库引用: android java读写yaml文件 java修改yaml文件 YamlFile: 修改yaml文件方法2 Yaml: 删除值: 申请读写权限: <uses-permission android:name"and…...
科学计算器网站Desmos网站
科学计算器网站Desmos网站 有时在学习工作或者生活中,需要用到计算问题,但由于电脑上没有安装相应的专业软件,难以计算有的问题,因而,本文推荐一种免费的在线计算网站Desmos。 一、Desmos网址 Desmos官网的地址为&a…...
结构体-时间的计算
任务描述 本关任务需要你编写函数计算一个时间之前“xx小时xx分xx秒”的时间是多少。 以24小时制的格式记录当前时间,譬如“09:19:52”,表示上午9点19分52秒,则“1小时20分30秒”前的时间应该是“同一天”的“07:59:22”。 提示:…...
pt24django教程
静态文件访问 不能与服务器端做动态交互的文件都是静态文件,如: 图片,css,js,音频,视频,html文件(部分) 静态文件配置 在 settings.py 中配置一下两项内容: STATIC_URL 静态文件的访问路径,通过哪个url地址找静态文件 ,STATIC_URL ‘/s…...
Golang开发-new关键字
在Go语言中,new关键字用于创建一个新的零值对象,并返回指向该对象的指针。它是Go语言中用于分配内存的一种方式。 new关键字的语法如下: ptr : new(Type)其中,Type表示要创建的对象的类型,ptr是指向新对象的指针。 …...
遗传算法与粒子群算法的Python实现
遗传算法本文应用的是 python geatpy module粒子群算法本文应用的是 python pyswarm module 遗传算法 它的不等约束是...<0 import geatpy as ea import numpy as npea.Problem.single def evalVars(Vars): x1 Vars[0]x2 Vars[1]x3 Vars[2]x4 Vars[3]f (x1 2)**2 \…...
无涯教程-JavaScript - ASINH函数
描述 ASINH函数返回数字的反双曲正弦值。反双曲正弦是其双曲正弦为number的值,即ASINH(SINH(number))等于number。 语法 ASINH (number)争论 Argument描述Required/OptionalNumberAny real number.Required Notes 如果指定的数字未被识别为数字值,则ASIN返回#VALUE!错误 …...
ActiveMQ面试题(一)
文章目录 前言一、什么是ActiveMQ二、ActiveMQ 服务器宕机怎么办?三、丢消息怎么办四、持节化消息非常慢五、消息的不均匀消费总结 前言 什么是ActiveMQActiveMQ 服务器宕机怎么办?丢消息怎么办持节化消息非常慢消息的不均匀消费 一、什么是ActiveMQ a…...
node:glob语法以及常用的文件查找库glob、fast-glob
背景 前端开发中,我们经常会看到一种配置语法,一般出现在 gitignore里、webpack 配置里、vscode查找文件的时候,如下: ?.js **/*.js dist/**/*.js这种语法其实叫 glob。 glob 历史 glob 来自于 Linux。 1975 年发行的 unix …...
饲料添加剂 微生物 屎肠球菌
声明 本文是学习GB 7300.503-2023 饲料添加剂 第5部分:微生物 屎肠球菌. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 1 范围 本文件规定了饲料添加剂屎肠球菌的技术要求、采样、检验规则、标签、包装、运输、贮存和保质 期࿰…...
二叉搜索树经典笔试题【力扣、牛客】
文章目录 1.根据二叉树创建字符串2. 二叉树的层序遍历3.二叉树的层序遍历Ⅱ4.二叉树的最近公共祖先1.法一:定位p、q在左还是右 分类讨论2.法二:利用stack求出p、q路径 求相交值 5.二叉搜索树与双向链表1.法一:递归:递归过程修正指…...
docker系列(1) - docker环境篇
文章目录 1. docker环境1.1 docker安装1.2 阿里云镜像加速器1.2 docker管理工具(portainer)1.3 docker网络1.3.1 网络说明1.3.2 创建指定网关的网络 1. docker环境 1.1 docker安装 #CentOS 6 rpm -iUvh http://dl.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.noar…...
web安全漏洞-SQL注入攻击实验
实验目的 学习sql显注的漏洞判断原理掌握sqlmap工具的使用分析SQL注入漏洞的成因 实验工具 sqlmap是用python写的开源的测试框架,支持MySQL,Oracle,PostgreSQL,Microsoft SQL Server,Microsoft Access,I…...
直接插入排序(C++实现)
文章目录 1. 基础概念🍑 内部排序和外部排序 2. 直接插入排序3. 动图演示4. 代码实现5. 性能分析 无论是日常生活还是很多科学领域当中,排序都是会经常面对的问题,比如按成绩对学校的学生排序,按薪水多少对公司员工排序等。 根据…...
【k8s】Pod 的钩子
Kubernetes(K8s)中的 Pod 可以使用以下几种勾子(钩子)来执行在容器生命周期的不同阶段运行的操作: PostStart(启动后):该勾子在容器启动之后立即运行。它可以用于在容器内执行一些初…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践
作者:吴岐诗,杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言:融合数据湖与数仓的创新之路 在数字金融时代,数据已成为金融机构的核心竞争力。杭银消费金…...
django blank 与 null的区别
1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是,要注意以下几点: Django的表单验证与null无关:null参数控制的是数据库层面字段是否可以为NULL,而blank参数控制的是Django表单验证时字…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
