对KMP简单的理解
声明:下边的例子均表示下标从1开始的数组
ne数组的定义:
next[i] 就是使子串 s[1…i] 有最长相等前后缀的前缀的最后一位的下标。ne[i]也可以表示相等子串的长度
准备执行j=ne[j]时, 表示当前s[i]!=p[j+1] , 如果ne[j]=1 ,那么下一次匹配从p数组的第二个字符(也就是p[j+1])开始比较是否s[i]=p[j+ 1]
a b a b a b c a b
1 2 3 4 5 6 7 8 9
a b a b a b c a b
1 2 3 4 5 6 7 8 9
同理:ne数组的建立也是这样的,从数组的第二个字符开始枚举,因为第一个字符没有相同的字串,从i=2,j=0,开始枚举,
i=2,j=0 p[i] != p[j+1] ne[2]=0;
i=3,j=0 p[i]==p[j+1] ,j++,ne[3]=1;
i=4,j=1 p[i]==p[j+1] ,j++,ne[4]=2;
i=5,j=2 p[i]==p[j+1] ,j++,ne[5]=3;
i=6,j=3 p[i]==p[j+1] ,j++,ne[6]=4;
i=7,j=4 p[i]!=p[j+1] (此时两者不相等,那么执行j=ne[j] ,j=2,(刚才想样例时发现,为什么下一次比较不直接比较j+1=5,i=7呢?想了一下,其实这和在s数组中和p数组相等的字串问题一样,此时p数组才走到j=4,那么 j 退一下,只能退到 j = ne[i] ) 发现p[i]!=p[j+1],继续执行j=ne[j] ,j=0,所以下一次比较就从0开始比较)
(其实直接看ne数组的更新比较绕,可以对比s数组和p数组的匹配,两者其实是一样的,就上边最后一步 j -----> 0来说,下一次s数组的s[i]要和p数组的p[1]比较)

KMP数组的应用

分析:观察样例发现,每次后边加的都是剔除字符串t的最长的前缀和后缀相等的子串后剩下的字符串,那么就可以用KMP求最长字串的长度(也就是 ne[n] )
#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 55;int n, m;
char str[N];
int ne[N];int main()
{scanf("%d%d", &n, &m);scanf("%s", str + 1);for (int i = 2, j = 0; i <= n; i ++ ){while (j && str[i] != str[j + 1]) j = ne[j];if (str[i] == str[j + 1]) j ++ ;ne[i] = j;}// cout<<ne[n]<<endl;printf("%s", str + 1);for (int i = 0; i < m - 1; i ++ )printf("%s", str + 1 + ne[n]);return 0;
}
相关文章:
对KMP简单的理解
声明:下边的例子均表示下标从1开始的数组 ne数组的定义: next[i] 就是使子串 s[1…i] 有最长相等前后缀的前缀的最后一位的下标。ne[i]也可以表示相等子串的长度 准备执行jne[j]时, 表示当前s[i]!p[j1] , 如果ne[j]1 ,那么下…...
Hibernate不是过时了么?SpringDataJpa又是什么?和Mybatis有什么区别?
一、前言 ps: 大三下学期,拿到了一份实习。进入公司后发现用到的技术栈有Spring Data Jpa\Hibernate,但对于持久层框架我只接触了Mybatis\Mybatis-Plus,所以就来学习一下Spring Data Jpa。 1.回顾MyBatis 来自官方文档的介绍:MyBatis 是一款…...
数学建模拓展内容:卡方检验和Fisher精确性检验(附有SPSS使用步骤)
卡方检验和Fisher精确性检验卡方拟合度检验卡方独立性检验卡方检验的前提假设Fisher精确性检验卡方拟合度检验 卡方拟合度检验概要:卡方拟合度检验也被称为单因素卡方检验,用于检验一个分类变量的预期频率和观察到的频率之间是否存在显著差异。 卡方拟…...
【Python学习笔记之七大数据类型】
Python数据类型:Number数字、Boolean布尔值、String字符串、list列表、tuple元组、set集合、dictionary字典 int整数 a1 print(a,type(a))float浮点数 b1.1 print(b,type(b))complex复数 c100.5j print(c,type(c))bool布尔值:True、False,true和false并非Python…...
Android系统之onFirstRef自动调用原理
前言:抽丝剥茧探究onFirstRef究竟为何在初始化sp<xxx>第一个调用?1.onFirstRef调用位置<1>.system/core/libutils/RefBase.cpp#include <utils/RefBase.h>//1.初始化强指针 void RefBase::incStrong(const void* id) const {weakref_i…...
ipv6上网配置
一般现在的宽带都已经支持ipv6了,但是需要一些配置才能真正用上ipv6。记录一下配置过程。 当前测试环境为移动宽带,光猫下面接了一个路由器,家里所有的设备都挂到这个路由器下面的。 1. 光猫改桥接 光猫在使用路由模式下,ipv6无…...
python实现聚类技术—复杂网络社团检测 附完整代码
实验内容 某跆拳道俱乐部数据由 34 个节点组成,由于管理上的分歧,俱乐部要分解成两个社团。 该实验的任务即:要求我们在给定的复杂网络上检测出两个社团。 分析与设计 实验思路分析如下: 聚类算法通常可以描述为用相似度来衡量两个数据的远近,搜索可能的划分方案,使得目标…...
如何判断两架飞机在汇聚飞行?(如何计算两架飞机的航向夹角?)内含程序源码
ok,在开始一切之前,让我先猜一猜,你是不是想百度“二维平面下如何计算两个移动物体的航向夹角?”如果是,那就请继续往下看。 首先,我们要明确一个概念:航向角≠航向夹角!࿰…...
Scipy稀疏矩阵bsr_array
文章目录基本原理初始化内置方法基本原理 bsr,即Block Sparse Row,bsr_array即块稀疏行矩阵,顾名思义就是将稀疏矩阵分割成一个个非0的子块,然后对这些子块进行存储。通过输入维度,可以创建一个空的bsr数组࿰…...
LeetCode笔记:Weekly Contest 332
LeetCode笔记:Weekly Contest 332 1. 题目一 1. 解题思路2. 代码实现 2. 题目二 1. 解题思路2. 代码实现 3. 题目三 1. 解题思路2. 代码实现 4. 题目四 1. 解题思路2. 代码实现 比赛链接:https://leetcode.com/contest/weekly-contest-332/ 1. 题目一…...
autox.js在vscode(win7)与雷神模拟器上的开发环境配置
目录 下载autox.js 安装autox.js? 在电脑上搭建autox.js开发环境 安装vscode 安装autox.js插件 雷神模拟器连接vscode 设置雷神模拟器IP 设置autox.js应用IP地址等 下载autox.js 大体来说,就是一个运行在Android平台上的JavaScript 运行环境 和…...
创建阿里云物联网平台
创建阿里云物联网平台 对云平台设备创建过程做记录,懒得再看视频 文章参考视频:https://www.bilibili.com/video/BV1jP4y1E7TJ?p26&vd_source50694678ae937a743c59db6b5ff46c31 阿里云:https://www.aliyun.com 1.物联网平…...
【链式二叉树】数据结构链式二叉树的(万字详解)
前言: 在上一篇博客中,我们已经详解学习了堆的基本知识,今天带大家进入的是二叉树的另外一种存储方式----“链式二叉树”的学习,主要用到的就是“递归思想”!! 本文目录1.链式二叉树的实现1.1前置说明1.2结…...
Koa2篇-简单介绍及使用
一.简介koa2是基于 Node.js 平台的下一代 web 开发框架, 致力于成为一个更小、更富有表现力、更健壮的 Web 框架。 可以避免异步嵌套. express中间件是异步回调,Koa2原生支持async/await二.async/awaitconst { rejects } require("assert"); const { resolve } req…...
Linux ALSA 之十一:ALSA ASOC Path 完整路径追踪
ALSA ASOC Path 完整路径追踪一、ASoc Path 简介二、ASoc Path 完整路径2.1 tinymix 设置2.2 完整路径 route一、ASoc Path 简介 如前面小节所描述,ASoc 中 Machine Driver 是 platform driver 和 codec driver 的粘合剂,audio path 离不开 FE/BE/DAI l…...
【Spring Cloud总结】1、服务提供者与服务消费者快速上手
目录 文件结构 代码 1、api 1.1实体类(Dept ) 1.2数据库 2、provider 2.1 DeptController 2.2 DeptDao 2.3 DeptService 2.4 DeptServiceImpl 2.5 application.yml 3、consumer 3.1 ConfigBean 3.2 DeptConsumerController 测试 1.启动…...
若依项目学习之登录生成验证码
若依项目学习之登录生成验证码 使用DefaultKaptcha生成验证码 /*** 验证码配置* * author ruoyi*/ Configuration public class CaptchaConfig {/*** 生成字符类型的验证码**/Bean(name "captchaProducer")public DefaultKaptcha getKaptchaBean(){DefaultKaptcha…...
计算机网络5:数据在两台计算机之间是怎样传输的?
数据在两台计算机之间的传输总的来说包括了封装和解封两个过程 封装(5层协议) 以传送一张图片为例 **应用层:**将jpg格式的图片数据转化成计算机可以识别的0101的二进制的比特流 **传输层:**将应用层传输下来的数据进行分段&…...
就现在!为元宇宙和Web3对互联网的改造做准备!
欢迎来到Hubbleverse 🌍 关注我们 关注宇宙新鲜事 📌 预计阅读时长:8分钟 本文仅代表作者个人观点,不代表平台意见,不构成投资建议。 如今,互联网是各种不同的网站、应用程序和平台的集合。由于彼此分离…...
【mysql数据库】
目录SQL数据库分页聚合函数表跟表之间的关联关系SQL中怎么将行转成列SQL注入将一张表的部分数据更新到另一张表WHERE和HAVING的区别索引索引分类如何创建及保存MySQL的索引?怎么判断要不要加索引?索引设计原理只要创建了索引,就一定会走索引吗…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Python 包管理器 uv 介绍
Python 包管理器 uv 全面介绍 uv 是由 Astral(热门工具 Ruff 的开发者)推出的下一代高性能 Python 包管理器和构建工具,用 Rust 编写。它旨在解决传统工具(如 pip、virtualenv、pip-tools)的性能瓶颈,同时…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
MySQL 8.0 事务全面讲解
以下是一个结合两次回答的 MySQL 8.0 事务全面讲解,涵盖了事务的核心概念、操作示例、失败回滚、隔离级别、事务性 DDL 和 XA 事务等内容,并修正了查看隔离级别的命令。 MySQL 8.0 事务全面讲解 一、事务的核心概念(ACID) 事务是…...
