KMP 详解
KMP数组存的是什么
对于一个字符串 b,下标从1开始。
则kmp[i]表示 以i结尾的连续子串 = s的前缀的最大值(等价于前缀最大结尾处)
如何求KMP
假设 i 以前的KMP都被求出来了。
j 表示上一个字符可以成功匹配的长度(等价于下标)
如果b[j+1] != b[i]下一个位置匹配不上(即不能成为前缀)
则,让j = kmp[j] 即成为以j结尾的 连续子串 的 最长前缀 尾部的下标
退出循环后,若还能匹配上则j++(本质是,加上i的贡献。因为j = 0时可能匹配不上)
然后让kmp[i] = j即可。
运用kmp
和求kmp差不多,如果匹配不上,求让a[i]和以j结尾的连续子串的最长前缀匹配。(放宽要求)
算法正确性证明
用哲学的话来说就是,每一次失败都会让我变得更强大。
当匹配不上时,匹配串b至少会前移1位,由指针的思想。O(n)可证。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
int kmp[N];
string a,b;
int j;
int main(){cin>>a>>b;a = " "+a;b = " "+b;for(int i = 2;i < b.size();i++){while(j&&b[j+1] != b[i]){j = kmp[j];}if(b[j+1] == b[i])j++;kmp[i] = j;}j = 0;for(int i = 1;i < a.size();i++){while(j&&a[i] != b[j+1]){j = kmp[j];}if(b[j+1] == a[i])j++;if(j == b.size()-1){cout<<i-(b.size()-1)+1<<endl;j=kmp[j];}}for (int i=1;i < b.size();i++)cout<<kmp[i]<<" ";return 0;
}

相关文章:
KMP 详解
KMP数组存的是什么 对于一个字符串 b,下标从1开始。 则kmp[i]表示 以i结尾的连续子串 s的前缀的最大值(等价于前缀最大结尾处) 如何求KMP 假设 i 以前的KMP都被求出来了。 j 表示上一个字符可以成功匹配的长度(等价于下标) …...
go语言并发编程-超详细mutex解析
文章目录 1 go语言并发编程学习-mutex1.1 学习过程1.2 如何解决资源并发访问的问题?【基本用法】1.2.1 并发访问带来的问题1.2.1.1 导致问题的原因 1.2.2 race detector检查data race1.2.3 mutex的基本实现机制以及使用方法1.2.3.1 具体使用-11.2.3.1 具体使用-2 1 …...
VirtualBox Debian 自动安装脚本
概览 相较于原脚本(安装目录/UnattendedTemplates/debian_pressed.cfg)更新如下内容: 配置清华镜像源配置仅主机网卡(后续只需添加仅主机网卡即可)配置Root用户远程登录配置用户sudo组 脚本 debian_pressed.cfg ##…...
最好的开放式耳机?五款红榜开放式耳机推荐!
面对众多的开放式耳机选项,消费者可能会感到难以抉择。买耳机不一定要买最贵最好的,但是一定要选最适合自己的,为了使选择过程更加容易,我提供了一些建议,推荐了几款既适合日常使用又佩戴舒适的热门开放式耳机。 开放式…...
线性代数之线性方程组
目录 线性方程组 1. 解的个数 齐次线性方程组: 非齐次线性方程组: 2. 齐次线性方程组的解 3. 非齐次线性方程组的解 4. 使用 Python 和 NumPy 求解线性方程组 示例代码 齐次线性方程组 非齐次线性方程组 示例结果 齐次线性方程组 非齐次线性…...
速盾:怎么查看是否使用cdn服务?
CDN(Content Delivery Network),即内容分发网络,是一种加速网络内容传输的技术。通过在全球各地建立分布式的节点服务器,将网站的静态资源缓存到最近的节点服务器上,使用户可以从离自己地理位置最近的节点服…...
828华为云征文|采用Flexus云服务器X实例部署RTSP直播服务器
一、前言 这篇文章讲解: 采用华为云最新推出的Flexus云服务器X实例搭建RTSP服务器,完成视频直播需求。 随着实时视频流传输需求的增长,RTSP(实时流协议)服务器成为了许多视频监控、直播和多媒体应用的核心组件。在当…...
Spring Cloud Gateway(二)
Spring Cloud Gateway(二) 文章目录 Spring Cloud Gateway(二)Gateway工作原理为什么使用API网关高并发Gateway性能优化 Gateway工作原理 Spring Cloud Gateway旨在为微服务架构提供简单、有效并且统一的API路由管理方式。它不仅…...
docker 简易入门
# docker 简易入门 docker由几个组成部分 docker client: 即 docker 命令行工具 docker host: 宿主机,docker daemon 的运行环境服务器 docker daemon: docker 的守护进程,docker client 通过命令行与 docker daemon 交互 container: 最小型的一个操…...
【看雪-注册安全分析报告】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 暴力破解密码,造成用户信息泄露短信盗刷的安全问题,影响业务及导致用户投诉带来经济损失,尤其是后付费客户,风险巨大,造成亏损无底洞…...
记录一个前端学习小组的收集的模版
问题1:输入“您的姓名”,选择“短答案”作为问题类型。问题2:输入“您是否愿意继续参加前端学习小组?”,选择“单选”作为问题类型,并添加选项“是”和“否”。问题3:输入“如果您选择‘是’&am…...
Rk3588 Android12 AIDL 开发
AIDL (Android Interface Definition Language) 和 HIDL (HAL Interface Definition Language) 都是 Android 系统中用于定义接口的工具,但它们有不同的用途和特性。 AIDL (Android Interface Definition Language) 用途: 主要用于应用程序之间的进程间…...
两个长整数字符串求和(不允许使用ES6+)
两个长整数字符串求和(不允许使用ES6), 面试手撸代码遇到到这个问题 1. 实现方式第一种 // 短整数字符串前边补 0; num需要补 0 的短整数字符串, len 长整数字符串的长度 function fillZero (num, len) {let str num.toString();if (str.length < len) {str 0.repeat(…...
11 Java 方法引用、异常处理、Java接口之函数式编程(接口知识补充Function<T,R>、BiFunction<T, U, R>和自定义泛型接口)
文章目录 前言一、Java接口之函数式编程 --- 接口知识补充1 Function<T,R>泛型接口2 BiFunction<T, U, R>泛型接口3 自定义泛型函数式编程接口4 使用lambda表达式、方法引用进行函数式编程二、方法引用1 方法引用初体验(以Array.sort()方法为例)(1)什么是方法引…...
深入探索 Go 语言的编译器与垃圾回收机制
Go 编译器 Go 编译器是通过 go 工具执行的,这个工具的功能不仅仅是生成可执行文件。你可以使用 go tool compile 命令来编译一个 Go 源文件。这个操作将生成一个目标文件,也就是 .o 后缀的文件。以下是在 macOS Mojave 系统上执行的命令和结果展示&…...
2024国赛数学建模-模拟火算法(MATLAB 实现)
模拟退火算法 1.1 算法原理 模拟退火算法的基本思想是从一给定解开始 ,从邻域 中随机产生另一个解 ,接受 Metropolis准则允许目标函数在 有限范围内变坏 ,它由一控制参数 t决定 ,其作用类似于物 理过程中的温度 T,对于控制参数的每一取值 ,算法持续进 行“产生 —判断 —接受…...
YOLOv8 只检测人 只画框不要标签
参考了这个:YOLOv8只检测人(或其他一种或者多种类别)_yolov8只检测指定类别-CSDN博客 1. 只检测人:predict的时候指定参数classes[0] 2. 只画框不要标签:plot的时候传入labelsFalse 3. 标签中去掉置信度:…...
如何将网络安全防范游戏化
组织对威胁的准备和恢复能力跟不上网络犯罪分子的进步。 一些首席执行官仍然认为网络安全需要偶尔干预,而不是持续关注。 但对于许多公司来说,情况并非如此;网络威胁准备需要协调一致的培训工作,因此网络安全团队在攻击发生时已…...
Qt QGraphicsView实现图片放缩、鼠标拖动移动、鼠标点位置放大缩小_图片查看
QtQGraphicsView实现图片放缩、鼠标拖动移动、鼠标点位置放大缩小 头文件: #ifndef TIMGWIDGET_H #define TIMGWIDGET_H#include <QGraphicsItem> #include <QMainWindow> #include <QObject> #include <QWidget>// class TImgWidget : pu…...
Percona Toolkit 神器全攻略(复制类)
Percona Toolkit 神器全攻略(复制类) Percona Toolkit 神器全攻略系列共八篇,前文回顾: 前文回顾Percona Toolkit 神器全攻略Percona Toolkit 神器全攻略(实用类)Percona Toolkit 神器全攻略(配…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
