当前位置: 首页 > news >正文

算法学习系列(十一):KMP算法

目录

  • 引言
  • 一、算法概念
  • 二、题目描述
  • 三、思路讲解
  • 三、代码实现
  • 四、测试

引言

这个KMP算法就是怎么说呢,就是不管算法竞赛还是找工作笔试面试,都是非常爱问爱考的,其实也是因为这个算法比较难懂,其实就是很难,所以非常个人的一个思维逻辑吧,反正就是用来区分人的,我会你不会,那么我就比你牛逼,所以那就开始吧。

一、算法概念

这个KMP算法就是用来匹配字符串的,在一个字符串中是否有另一个字符串的存在,如果存在返回原始字符串中的初始下标

二、题目描述

给定一个字符串 S,以及一个模式串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。模式串 P 在字符串 S 中多次作为子串出现。求出模式串 P 在字符串 S 中所有出现的位置的起始下标。输入格式
第一行输入整数 N,表示字符串 P 的长度。
第二行输入字符串 P。
第三行输入整数 M,表示字符串 S 的长度。
第四行输入字符串 S。输出格式
共一行,输出所有出现位置的起始下标(下标从 0 开始计数),整数之间用空格隔开。数据范围
1≤N≤1051≤M≤106输入样例:
3
aba
5
ababa输出样例:
0 2

三、思路讲解

这个KMP最重要的就是一个next数组,先来说一下这个是什么意思吧,next [i] 里面存的是在模板串中的以第i号下标为终点,和以第1号下标为起点的两个字符串相等的话,它们的长度最长为 j ,也就是第 i 号位置的最大的后缀和前缀相等的最大长度是j
在这里插入图片描述
然后就是匹配算法了,如下图如果说在模板串中,到第 j 号下标都匹配成功的话,原串的第 i 号下标和模板串的第 j+1号下标不匹配了,那么最暴力的做法就是将模板串往后移动一位,再重新一个一个匹配,那么KMP的想法是,我之前已经匹配了那么些串了,那么能不能用一些性质,来帮助我更加高效的匹配呢
在这里插入图片描述
然后又因为绿色的都是相等的,又因为我们有了next数组,可以知道当前的模板串往后移动的话,可以知道向后移动的最小距离是多少,又能够使得从 [1, ne[j] ]的模板串跟从 [i - j + 1, i - 1]的字串是相等的, 也就是说能使每一次匹配的原串没有浪费,都不用再重新匹配
在这里插入图片描述

三、代码实现

然后这个KMP的话,下标一般是从1开始的

#include <iostream>using namespace std;const int N = 100010, M = 1000010;int n, m;
char p[N], s[M];
int ne[N];int main()
{cin >> n >> p + 1 >> m >> s + 1;//求next数组for(int i = 2, j = 0; i <= n; ++i)  //因为ne[1]就是0可以直接从2开始{while(j && p[i] != p[j+1]) j = ne[j];if(p[i] == p[j+1]) j++;ne[i] = j;}for(int i = 1, j = 0; i <= m; ++i){while(j && s[i] != p[j+1]) j = ne[j];if(s[i] == p[j+1]) j++;if(j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}

四、测试

在这里插入图片描述

相关文章:

算法学习系列(十一):KMP算法

目录 引言一、算法概念二、题目描述三、思路讲解三、代码实现四、测试 引言 这个KMP算法就是怎么说呢&#xff0c;就是不管算法竞赛还是找工作笔试面试&#xff0c;都是非常爱问爱考的&#xff0c;其实也是因为这个算法比较难懂&#xff0c;其实就是很难&#xff0c;所以非常个…...

****Linux下Mysql的安装和配置

1、安装mysql 1.1、安装mysql sudo aptitude search mysql sudo apt-get install mysql-server mysql-client1.2、启动停止mysql: service mysql stop service mysql restart mysql -u debian-sys-maint -p mysql命令详细解释如下: 一、 启动方式 1、使用 service 启动…...

第十六节TypeScript 类

1、简介 TypeScript是面向对象的JavaScript。 类描述了所创建的对象共同的属性与方法。 2、类的定义 class class_name { // 类作用域 } 定义类的关键字是class&#xff0c;后面紧跟类名&#xff0c;类可以包含以下几个模块&#xff1a; 字段 – 字段是类里面声明的变量。字…...

RocketMQ的Docker镜像部署(以及Dashboard的部署、ACL配置)

RocketMQ的Docker镜像部署&#xff08;以及Dashboard、ACL&#xff09; 准备 包含RocketMQ部署&#xff08;NameServer、Broker&#xff09;、Dashboard、ACL拉取镜像 RocketMQ$ docker pull apache/rocketmq:5.1.4Dashboard$ docker pull apacherocketmq/rocketmq-dashboard…...

数据仓库【2】:架构

数据仓库【2】&#xff1a;架构 1、架构图2、ETL流程2.1、ETL -- Extract-Transform-Load2.1.1、数据抽取&#xff08;Extraction&#xff09;2.1.2、数据转换&#xff08;Transformation&#xff09;2.1.3、数据加载&#xff08; Loading &#xff09; 2.2、ETL工具2.2.1、结构…...

JavaScript函数表达式

JavaScript函数表达式是一种将函数赋值给变量的方式。函数表达式可以以匿名形式或具名形式存在。 匿名函数表达式&#xff1a; var func function() {// 函数的逻辑 }在上面的例子中&#xff0c;将一个匿名函数赋值给变量func。 具名函数表达式&#xff1a; var func fun…...

LabVIEW在齿轮箱故障诊断中的应用

LabVIEW在齿轮箱故障诊断中的应用 在现代机械工业中&#xff0c;齿轮箱作为重要的传动设备&#xff0c;其性能稳定性对整体机械系统的运行至关重要。故障的及时诊断和处理不仅保障了设备的稳定运行&#xff0c;还减少了维护成本。利用LabVIEW强大数据处理和仿真能力&#xff0…...

图片转excel:“保留数字格式”在什么场景下该勾

保留数字格式是什么意思呢&#xff1f;顾名思义&#xff0c;就是将转出来的数字保留为数字格式&#xff0c;而不是文本格式。我们知道&#xff0c;OCR程序将图片上的文字识别为电脑可编辑的文字后&#xff0c;如果导入到excel不加处理&#xff0c;则单个数字过长的文字就会被ex…...

SpringMVC:整合 SSM 下篇

文章目录 SpringMVC - 05整合 SSM 下篇一、设计页面1. 首页&#xff1a;index.jsp2. 展示书页面&#xff1a;showBooks.jsp3. 增加书页面&#xff1a;addBook.jsp4. 修改书页面&#xff1a;updateBook.jsp5. 总结 二、控制层1. 查询全部书2. 增加书3. 修改书4. 删除书5. 搜索书…...

[2023-年度总结]凡是过往,皆为序章

原创/朱季谦 2023年12月初&#xff0c;傍晚&#xff0c;在深圳的小南山看了一场落日。 那晚我们坐在山顶的草地上&#xff0c;拍下了这张照片——仿佛在秋天的枝头上&#xff0c;结出一颗红透的夕阳。 这一天很快就会随着夜幕的降临&#xff0c;化作记忆的碎片&#xff0c;然…...

OpenCV之像素操作

我们首先了解一下什么是像素&#xff0c;计算机中是如何存储图像&#xff0c;以及opencv是如何表示图像的。 像素&#xff1a; 像素是指由图像的小方格即所谓的像素(pixel)组成的&#xff0c;这些小方块都有一个明确的位置和被分配的色彩数值&#xff0c;而这些一小方格的颜色…...

Transfer Learning(迁移学习)

1. 什么是迁移学习 迁移学习(Transfer Learning)是一种机器学习方法&#xff0c;就是把为任务 A 开发的模型作为初始点&#xff0c;重新使用在为任务 B 开发模型的过程中。迁移学习是通过从已学习的相关任务中转移知识来改进学习的新任务&#xff0c;虽然大多数机器学习算法都…...

NPM 的使用技巧:简化 JavaScript 开发和依赖管理

前言 NPM&#xff08;Node Package Manager&#xff09;是 JavaScript 生态系统中最流行的包管理工具之一。本文将介绍一些有用的 NPM 使用技巧&#xff0c;帮助开发者更好地利用 NPM 管理项目依赖、执行脚本、发布自己的包以及解决常见问题。 1. 初始化项目 使用 NPM 初始化…...

统计和绘图软件GraphPad Prism mac功能特点

GraphPad Prism mac是一款专业的统计和绘图软件&#xff0c;主要用于生物医学研究、实验设计和数据分析。 GraphPad Prism mac功能和特点 数据导入和整理&#xff1a;GraphPad Prism 可以导入各种数据格式&#xff0c;并提供直观的界面用于整理、编辑和管理数据。用户可以轻松…...

WWW 指南-万维网联盟(World Wide Web)

WWW - 万维网联盟 WWW通常称为网络。 web是一个世界各地的计算机网络。 电脑在Web上使用标准语言沟通。 万维网联盟&#xff08;W3C&#xff09;制定了Web标准 什么是WWW&#xff1f; WWW 代表 World Wide Web(万维网)万维网常常被称为 网络网络是世界各地的计算机网络网络中…...

Linux网络编程之TCP/IP实现高并发网络服务器设计指南

目录 引言&#xff1a; 多进程服务器 例程分享&#xff1a; 多线程服务器 例程分享&#xff1a; I/O多路复用服务器 select 例程分享&#xff1a; poll 例程分享&#xff1a; epoll 例程分享&#xff1a; 总结建议 引言&#xff1a; 随着互联网的迅猛发展&#xff…...

【SpringBoot实战】基于阿里云实现文件上传

【SpringBoot实战】基于阿里云实现文件上传 在实际项目开发中&#xff0c;不可避免地会使用到阿里云OSS进行文件存储。尽管阿里云有详细的开发文档&#xff0c;但本篇博客的目的是让我们能够用简明的代码快速实现这个功能。 引入依赖 <dependencies><!-- 阿里云oss…...

大数据技术学习笔记(十一)—— Flume

目录 1 Flume 概述1.1 Flume 定义1.2 Flume 基础架构 2 Flume 安装3 Flume 入门案例3.1 监控端口数据3.2 实时监控单个追加文件3.3 实时监控目录下多个新文件3.4 实时监控目录下的多个追加文件 4 Flume 进阶4.1 Flume 事务4.2 Flume Agent 内部原理4.3 Flume 拓扑结构4.3.1 简单…...

电路设计时,继电器线圈、风扇电机绕组等感性负载必须有续流二极管。

续流二极管(也常被称为“自由轮流二极管”或“反向并联二极管”)在感性负载电路中的应用非常重要,尤其是在继电器线圈、风扇电机绕组等设备中。感性负载是指那些在其线圈中会产生感应电动势的负载,例如电动机、变压器和继电器等。当这些设备的电源被切断时,它们的线圈会因…...

Mongodb基础介绍与应用场景

NoSql 解决方案第二种 Mongodb MongoDB 是一款开源 高性能 无模式的文档型数据库 当然 它是NoSql数据库中的一种 是最像关系型数据库的 非关系型数据库 首先 最需要注意的是 无模式的文档型数据库 这个需要后面我们看到它的数据才能明白 其次是 最像关系型数据库的非关系型数据…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...