kmp算法(c++)

kmp算法的简单介绍

在这里插入图片描述

从主串中快速找到与要找的串的相同位置
如果使用暴力算法去求解这个问题,时间复杂度为O(i*j) => 很大
在这里插入图片描述
kmp算法则是对这类问题的优化
因整理过于麻烦,,详细的介绍可以参照这篇博客,,花时间看完就明白了,写的很棒!!!
kmp算法详细介绍
下面是自己学习的一些注意的地方,主要是针对于代码模版来讲解。

next[i]的介绍

以i为终点的后缀和从1开始的前缀相等,并且保证后缀的长度最长

ex: next[ i ] = j
在这里插入图片描述

p[ 1 , j] = p[ i - j + 1,i]
//p数组中从1到j这一段与 从i-j+1到i这一段相等 

在这里插入图片描述

当上面数组移动到S[i] 下面移动到p[j + 1]的时候,s[i] != p[j+1]

此时就要将 红颜色的线从前往后移动 要计算的是 从前往后最少需要移动多少 直接调用next[j]

移动完成之后 就变成第三段线段 从原本的j变成next[j]

然后就继续比较next[j]下面一位跟s[i]

在这里插入图片描述
最终就一直递归上面的操作 直到完全匹配为止

代码分析:

1、kmp匹配的过程
// j=1定义是因为  在比较的时候一直是p[j] 与 s[i+1]进行比较
//所以j要多加一个1去错位for (int i = 1, j = 0; i <= m; i++){// while(j)的意思是j没有退回到起点 //j如果退回到起点(j == 0)含义就是需要重新开始匹配//s[i] != p[j+1] 出现不匹配的数字while(j && s[i] != p[j+1]) j = ne[j];//while循环结束有两种条件 //一个是j退回到了起点 //第二个是成功匹配了//如果他们两个已经匹配了,j就可以移动到下一个位置if(s[i] == p[j+1]) j++;if(j == n){//3.匹配成功}
}
2、求next过程

在这里插入图片描述
跟第一个线段的绿色点位置进行比较

如果不同,则j = ne[j] 仍然不相同就 j = ne[ne[j]]

一直匹配到相等为止

//next[1]不需要去注意  因为j是从0开始的
//如果next[1] 中的q前面只有一个数  也就是说next[1]  == 》 p[0]  for (int i = 2, j = 0; i <= n; i++){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j++;ne[i] = j;}
3、匹配成功的操作
			//输出起始位置printf("%d ",i - n);j = ne[j];

kmp字符串题目

给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 P 在字符串 S 中多次作为子串出现。

求出模式串 P 在字符串 S 中所有出现的位置的起始下标。

输入格式

第一行输入整数 N,表示字符串 P 的长度。

第二行输入字符串 P。

第三行输入整数 M,表示字符串 S 的长度。

第四行输入字符串 S。

输出格式

共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。

数据范围

1≤N≤1e5
1≤M≤1e6

输入样例:

3
aba
5
ababa

输出样例:

0 2

#include <iostream>using namespace std;
const int N = 10010, M = 100010;int n, m;
//
char p[N], s[M];
int ne[N];int main()
{// p + 1 跟 s + 1 表示下标从1开始cin >> n >> p + 1 >> m >> s + 1;//求next数组的过程for (int i = 2, j = 0; i <= n; i++){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j++;ne[i] = j;}//kmp的匹配过程// i是为了遍历s数组// j是从0开始做,每一次试图往前走,看能否走通for (int i = 1, j = 0; i <= m; i++){//j能否往后退 ,可以后退调用 j = ne[j]   while (j && s[i] != p[j + 1]) j = ne[j];//不能后退了之后还是不能走   条件都没有满足  i++ 看s串的下一个位置if (s[i] == p[j + 1]) j++;if (j == n){//匹配完成//输出起始位置printf("%d ",i - j);j = ne[j];}}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395838.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

第二十一节、敌人追击状态的转换

一、物理检测中的Boxcast 1、检测敌人Bool 当不知道一个函数的返回值是什么的时候 定义一个var变量 就知道了 二、状态切换 1、switch用法 2、新的语法糖写法

【MySQL】数据基本的增删改查操作

新增数据&#xff08;Create&#xff09; 在MySQL中&#xff0c;增加数据的操作主要使用 INSERT 语句。下面我们将分为两部分&#xff1a;单行数据插入和多行数据插入。 一、单行数据插入 全列插入&#xff1a; 当你要插入一行数据到表中并且要提供所有列的值时&#xff0c;可…

jmeter-beanshell学习16-自定义函数

之前写了一个从文件获取指定数据&#xff0c;用的时候发现不太好用&#xff0c;写了一大段&#xff0c;只能取出一个数&#xff0c;再想取另一个数&#xff0c;再粘一大段。太不好看了&#xff0c;就想到了函数。查了一下确实可以写。 public int test(a,b){return ab; } ctes…

剖析HTML 元素——WEB开发系列02

HTML元素是构成HTML文档结构的基本单位&#xff0c;定义了页面上的不同部分和内容。HTML元素可以包含不同类型的内容&#xff0c;如文本、图片、链接、表格等&#xff0c;每种元素都有其特定的用途和语义。通过组合和嵌套不同的HTML元素&#xff0c;可以创建复杂的网页结构和布…

java之如何爬取本地数据(利用正则表达式)

public class RegexDemo4 {public static void main(String[] args) {String s"程序员学习java&#xff0c;""电话&#xff1a;181512516758&#xff0c;18512508907" "或者联系邮箱&#xff1a;boniuitcast.cn&#xff0c;""座机电话&…

脱胎于 S 语言的R语言,Ross Ihaka 和 Robert Gentleman 和社区的力量让 R 在学术界与研究机构放光彩

R语言从一门用于统计学教学的编程语言&#xff0c;发展成为全球数据科学领域的重要工具&#xff0c;离不开其强大的功能、丰富的社区资源和开源精神。这些都离不开Ross Ihaka 和 Robert Gentleman 和 社区的力量。 在1990年代初&#xff0c;新西兰奥克兰大学的统计学教授Ross I…

6.3.面向对象技术-设计模式

设计模式 设计模式创建型模型速记口诀 结构型设计模式速记口诀 行为型设计模式速记口诀 练习题 设计模式 上午2-4分&#xff0c;记忆点很多 要具体了解推荐看书籍《大话设计模式》 架构模式&#xff1a;软件设计中的高层决策&#xff0c;例如C/S结构就属于架构模式&#xff0…

Dopple Labs 选择 Zilliz Cloud 作为安全高效的向量数据库

一直以来&#xff0c;我都十分赞同采用通用的标准来评估机器学习领域的技术。向量数据库领域也是如此。Zilliz 发布的性能测试对我有着很大的帮助。 ——Sam Butler Dopple.AI 机器学习总监 01.Dopple AI简介 Dopple Labs Inc. 是 Dopple.AI 的原厂&#xff0c;通过提供创新…

关于进程间通信的练习

1> 使用有名管道实现,一个进程用于给另一个进程发消息,另一个进程收到消息后,展示到终端上,并且将消息保存到文件上 一份 create.c #include<myhead.h>int main(int argc, const char *argv[]) {//创建一个管道文件if(mkfifo("./linux",0664)-1){perror(&qu…

RabbitMQ docker安装

后台配置文件 rabbitmq:image: rabbitmq:latestcontainer_name: rabbitmqports:- "5672:5672" # RabbitMQ server port- "15672:15672" # RabbitMQ management console portenvironment:RABBITMQ_DEFAULT_USER: adminRABBITMQ_DEFAULT_PASS: admin 若要打…

磁盘无法访问的危机与解救:数之寻软件的数据恢复之旅

在数字时代&#xff0c;磁盘作为数据存储的核心&#xff0c;承载着我们的工作文档、珍贵照片、个人视频等无价之宝。然而&#xff0c;当您试图访问某个磁盘时&#xff0c;却遭遇了“磁盘无法访问”的提示&#xff0c;这无疑是一场突如其来的数据危机。本文将深入探讨磁盘无法访…

【Kubernetes】k8s集群资源调度

目录 一、k8s的List-Watch机制 二、scheduler的调度过程 三、指定节点调度Pod 1.通过nodeName调度Pod 2.通过节点标签选择器调度Pod 3.通过亲和性调度Pod 1&#xff09;节点亲和性 2&#xff09;Pod 亲和性 四、污点(Taint) 和 容忍(Tolerations) 1.污点(Taint) 2.…

运行pytorch报异常处理

一、问题现象及初步定位&#xff1a; 找不到指定的模块。 Error loading "D:\software\python3\Lib\site-packages\torch\lib\fbgemm.dll 此处缺少.dll文件&#xff0c;首先下载文件依赖分析工具 Dependencies https://github.com/lucasg/Dependencies/tree/v1.11.1 之后下…

【大模型学习】多模态大模型进行偏好优化

一、简介 训练模型以理解并预测人类偏好是一项复杂的任务。传统方法如SFT&#xff08;监督微调&#xff09;通常需要较高的成本&#xff0c;因为这些算法需要对数据进行特定标签的标注。偏好优化&#xff08;Preference Optimization&#xff09;作为一种替代方案&#xff0c;…

【多线程-从零开始-捌】阻塞队列,消费者生产者模型

什么是阻塞队列 阻塞队里是在普通的队列&#xff08;先进先出队列&#xff09;基础上&#xff0c;做出了扩充 线程安全 标准库中原有的队列 Queue 和其子类&#xff0c;默认都是线程不安全的 具有阻塞特性 如果队列为空&#xff0c;进行出队列操作&#xff0c;此时就会出现阻…

C++ 重要特性探究

shared_from_this 使用分析 场景 类的成员函数需要获取指向自身的shared_ptr的时候类成员函数传递shared_ptr给其他函数或者对象的时候&#xff0c;目的是为了管理对象生命周期使用方法 首先类必须继承 std::enable_shared_from_this<T>必须使用 shared_from_this 获取指…

智慧交通:将物联网与人工智能完美融合

智慧交通是当今社会面临的一个重要挑战&#xff0c;也是人们生活质量提高的一个重要方面。通过将物联网技术与人工智能相结合&#xff0c;我们能够实现智慧交通系统的全面升级和优化&#xff0c;为人们带来更加便捷、高效和安全的出行体验。 在智慧交通领域&#xff0c;物联网…

电脑图片损坏打不开怎么办?能修复吗?

照片和视频是记录和保存现实生活中的事件的最好方式。由于手机储存空间有限&#xff0c;一般我们会把有纪念意义的照片放到电脑上进行保存&#xff0c;但有时难免会遇到照片被损坏打不开的情况&#xff0c;一旦遇到这种情况&#xff0c;先不要急&#xff0c;也不要因为照片打不…

【智能控制】第7章 神经网络理论基础,神经网络的分类,原理,发展,神经网络学习算法(北京航天航空大学)

目录 第7章 神经网络理论基础 1. 神经网络的发展 2. 神经网络原理 3. 神经网络的分类 (1) 前向网络 (2) 反馈网络 (3) 自组织网络 4. 神经网络学习算法 (1) 智能Hebb学习规则 (2) Delta&#xff08;δ&#xff09;学习规则 5. 神经网络的特征及…

【Mind+】 掌控板入门教程09 魔法之光

光是地球生命的来源&#xff0c;是人类生活的依据&#xff0c;更是人类认识外部世界的工具。在科技发达的今天&#xff0c;我们可以通过传感器来检测光&#xff0c;利用光帮助我们更好的生活。 今天就让我们一起通过几个小项目来感受光的魔法吧。 项目示例 掌控板…