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

《蓝桥杯每日一题》KMP算法·AcWing 141. 周期

1.题目描述

一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 55 个前缀,分别是 aababaabaaabaab

我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。

换言之,对于每一个从头开始的长度为 ii>1)的前缀,是否由重复出现的子串 A 组成,即 AAA…AA 重复出现 K 次,K>1)。

如果存在,请找出最短的循环节对应的 K 值(也就是这个前缀串的所有可能重复节中,最大的 K值)。

输入格式

输入包括多组测试数据,每组测试数据包括两行。

第一行输入字符串 S 的长度 N

第二行输入字符串 S

输入数据以只包括一个 0 的行作为结尾。

输出格式

对于每组测试数据,第一行输出 Test case # 和测试数据的编号。

接下来的每一行,输出具有循环节的前缀的长度 i 和其对应 K,中间用一个空格隔开。

前缀长度需要升序排列。

在每组测试数据的最后输出一个空行。

数据范围

2≤N≤1000000

输入样例:

3
aaa
4
abcd
12
aabaabaabaab
0

输出样例:

Test case #1
2 2
3 3
Test case #2
Test case #3
2 2
6 2
9 3
12 4

2.思路解析

不清楚kmp的可以先看下这篇

https://blog.csdn.net/m0_68055637/article/details/128596380

首先发现一个性质,对字符串S自己匹配求出next数组,然后根据定义,对于每一个i,s[i-next[i]+1~i]与s[1~next[i]]是相等的,而且不存在更大的next值满足条件.

既然如此的话,那么我们发现当i-next[i]能够整除i时候,那么s[1~i-next[i]]就是s[i-1]的最小循环元,至于次数那么也就是i/(i-next[i]).

3.代码

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);num=0;while(true){int n=sc.nextInt();if(n==0){break;}String str1=sc.next();num++;System.out.println("Test case #"+num);shuchu(n,str1);System.out.println();}}public static int num;public static void shuchu(int n,String str){//KMP的next的数组int[]next=new int[n];//此处next的数组是使用最大长度表实现 跟next[0]=-1意义不同next[0]=0;for (int i = 1,j=0; i <n ; i++) {while(j>0 &&str.charAt(j)!=str.charAt(i)){j= next[j-1];}if(str.charAt(i)==str.charAt(j)){j++;}next[i]=j;if(next[i]!=0){//i+1是当前字符串的长度 i+1-next[i]是这个字符串重复的子串的长度if((i+1)%(i+1-next[i])==0){ int temp=(i+1)/(i+1-next[i]); //个数System.out.println((i+1)+" "+temp);}}}}
}
感谢你能看完, 如有错误欢迎评论指正,有好的思路可以交流一波,如果对你有帮助的话,点个赞支持下

相关文章:

《蓝桥杯每日一题》KMP算法·AcWing 141. 周期

1.题目描述一个字符串的前缀是从第一个字符开始的连续若干个字符&#xff0c;例如 abaab 共有 55 个前缀&#xff0c;分别是 a&#xff0c;ab&#xff0c;aba&#xff0c;abaa&#xff0c;abaab。我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。换言之&#xff0c;对于每…...

URL介绍

前言Internet上的每一个网页都具有一个唯一的名称标识&#xff0c;通常称之为URL&#xff08;Uniform Resource Locator, 统一资源定位器&#xff09;。它是www的统一资源定位标志&#xff0c;简单地说URL就是web地址&#xff0c;俗称“网址”。一、URL概念URL是对互联网上得到…...

学习 Python 之 Pygame 开发魂斗罗(一)

学习 Python 之 Pygame 开发魂斗罗&#xff08;一&#xff09;Pygame回忆Pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音乐7. 图片翻转与…...

ARM uboot 源码分析8 - uboot的环境变量

一、uboot 的环境变量基础 1、环境变量的作用 (1) 让我们可以不用修改 uboot 的源代码&#xff0c;而是通过修改环境变量&#xff0c;来影响 uboot 运行时的一些数据和特性。譬如说&#xff0c;通过修改 bootdelay 环境变量&#xff0c;就可以更改系统开机自动启动时倒数的秒…...

【蓝牙mesh】Network协议层介绍

【蓝牙mesh】Network协议层介绍 Network层简介 上一章节我们讲解了蓝牙Mesh中Lower层的功能和数据格式。 Lower层的数据往下传输就到了网络层&#xff08;Network Layer&#xff09;。网络层定义了收到Lower层的数据后&#xff0c;如何对其进行判断、封装、加密、认证&#xf…...

基于遗传算法的配电网故障定位(Matlab代码实现)

&#x1f468;‍&#x1f393;个人主页&#xff1a;研学社的博客&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5;&#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密…...

Leetcode.1247 交换字符使得字符串相同

题目链接 Leetcode.1247 交换字符使得字符串相同 Rating &#xff1a; 1597 题目描述 有两个长度相同的字符串 s1和 s2&#xff0c;且它们其中 只含有 字符 "x"和 "y"&#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时…...

python语音识别whisper

一、背景 最近想提取一些视频的字幕&#xff0c;语音文案&#xff0c;研究了一波 二、whisper语音识别 Whisper 是一种通用的语音识别模型。它在不同音频的大型数据集上进行训练&#xff0c;也是一个多任务模型&#xff0c;可以执行多语言语音识别以及语音翻译和语言识别。 …...

Prometheus -- 浅谈Exporter

Prometheus系统 – Exporter原理 为什么我们需要Exporter&#xff1f; 广义上讲所有可以向Prometheus提供监控样本数据的程序都可以被称为一个Exporter。而Exporter的一个实例称为target&#xff0c;如下所示&#xff0c;Prometheus通过轮询的方式定期从这些target中获取样本…...

如何确定RocketMQ中消费者的线程大小

背景 随着物联网行业的发展、智能设备数量越来越多&#xff0c;随着设备活跃量过大&#xff0c;常常存在一些高并发的请求&#xff0c;形成了流量尖峰&#xff0c;过多的请求会压垮服务器&#xff0c;影响其他服务运行。因此&#xff0c;为了保护云端服务&#xff0c;需要对请求…...

OpenAPI SDK组件之Spring Aop源码拓展

Spring Aop 看这个分享的应该都用过Spring Aop&#xff0c;这里就不再过多介绍了它是什么了。 我抽取了Spring Aop的部分源码&#xff0c;通过它实现请求参数可变拦截&#xff0c;同时apisdk离开Spring框架&#xff0c;仍然可以正常运行。 讲拦截也好&#xff0c;通知也罢&a…...

蓝桥杯C/C++VIP试题每日一练之龟兔赛跑预测

&#x1f49b;作者主页&#xff1a;静Yu &#x1f9e1;简介&#xff1a;CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家&#xff0c;前端知识交流社区创建者 &#x1f49b;社区地址&#xff1a;前端知识交流社区 &#x1f9e1;博主的个人博客&#xff1a;静Yu的个人博客…...

为你的Vue2.x老项目安装Vite发动机吧

天下苦webpack久矣&#xff0c;相信作为前端开发者一定经历过在项目迭代时间较长的时候经历漫长等待的这一过程&#xff0c;每一次保存都会浪费掉大量时间&#xff0c;这是webpack这种机制所带来的问题。 于是&#xff0c;尤大为我们带来了新一代前端构建工具&#xff1a;vite…...

ZCMU--5012: 铺设道路(差分思路)

Description 春春是一名道路工程师&#xff0c;负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。 整段道路可以看作是 n 块首尾相连的区域&#xff0c;一开始&#xff0c;第 i 块区域下陷的深度为 di。  春春每天可以选择一段连续区间 [L,R]&…...

算法模板总结(自用)

算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之…...

【架构师】零基础到精通——架构发展

博客昵称&#xff1a;架构师Cool 最喜欢的座右铭&#xff1a;一以贯之的努力&#xff0c;不得懈怠的人生。 作者简介&#xff1a;一名Coder&#xff0c;软件设计师/鸿蒙高级工程师认证&#xff0c;在备战高级架构师/系统分析师&#xff0c;欢迎关注小弟&#xff01; 博主小留言…...

C++(20):三路比较运算符

C20增加了三路比较运算符<>&#xff08;戏称航天飞机运算符&#xff09;&#xff0c;用于对类的比较运算符进行统一的设计。有两种使用方式&#xff1a;默认比较对于某些类&#xff0c;如果按照其成员逐一比较即可决定比较运算符的值&#xff0c;那么可以使用默认的三路运…...

MySQL workbench 字符集、字符序的概念与联系

在数据的存储上&#xff0c;MySQL提供了不同的字符集支持。而在数据的对比操作上&#xff0c;则提供了不同的字符序支持。 MySQL提供了不同级别的设置&#xff0c;包括server级、database级、table级、column级&#xff0c;可以提供非常精准的设置。 什么是字符集、字符序&am…...

DBA之路---数据库启动与关闭过程

DBA之路—数据库启动与关闭过程 1、启动过程 oracle启动的四个状态 shutdown、就是数据库关闭状态。 nomount模式 #启动instance &#xff0c;读取参数文件、分配sga空间启动后台进程&#xff0c;打开alter日志和其他trace文件startup nomount #该模式下只会创建实例并不加…...

Shell文件包含

和其他语言一样&#xff0c;Shell 也可以包含外部脚本。这样可以很方便的封装一些公用的代码作为一个独立的文件。 一、语法格式 Shell 文件包含的语法格式如下&#xff1a; . filename # 注意点号(.)和文件名中间有一空格 或 source filename 在当前bash环境下读取并执行file…...

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...