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(启动后):该勾子在容器启动之后立即运行。它可以用于在容器内执行一些初…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
什么是库存周转?如何用进销存系统提高库存周转率?
你可能听说过这样一句话: “利润不是赚出来的,是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业,很多企业看着销售不错,账上却没钱、利润也不见了,一翻库存才发现: 一堆卖不动的旧货…...
苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
