《蓝桥杯每日一题》KMP算法·AcWing 141. 周期
1.题目描述
一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 55 个前缀,分别是 a,ab,aba,abaa,abaab。
我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。
换言之,对于每一个从头开始的长度为 i(i>1)的前缀,是否由重复出现的子串 A 组成,即 AAA…A (A 重复出现 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.题目描述一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 55 个前缀,分别是 a,ab,aba,abaa,abaab。我们希望知道一个 N 位字符串 S 的前缀是否具有循环节。换言之,对于每…...
URL介绍
前言Internet上的每一个网页都具有一个唯一的名称标识,通常称之为URL(Uniform Resource Locator, 统一资源定位器)。它是www的统一资源定位标志,简单地说URL就是web地址,俗称“网址”。一、URL概念URL是对互联网上得到…...
学习 Python 之 Pygame 开发魂斗罗(一)
学习 Python 之 Pygame 开发魂斗罗(一)Pygame回忆Pygame1. 使用pygame创建窗口2. 设置窗口背景颜色3. 获取窗口中的事件4. 在窗口中展示图片(1). pygame中的直角坐标系(2). 展示图片(3). 给部分区域设置颜色5. 在窗口中显示文字6. 播放音乐7. 图片翻转与…...
ARM uboot 源码分析8 - uboot的环境变量
一、uboot 的环境变量基础 1、环境变量的作用 (1) 让我们可以不用修改 uboot 的源代码,而是通过修改环境变量,来影响 uboot 运行时的一些数据和特性。譬如说,通过修改 bootdelay 环境变量,就可以更改系统开机自动启动时倒数的秒…...
【蓝牙mesh】Network协议层介绍
【蓝牙mesh】Network协议层介绍 Network层简介 上一章节我们讲解了蓝牙Mesh中Lower层的功能和数据格式。 Lower层的数据往下传输就到了网络层(Network Layer)。网络层定义了收到Lower层的数据后,如何对其进行判断、封装、加密、认证…...
基于遗传算法的配电网故障定位(Matlab代码实现)
👨🎓个人主页:研学社的博客💥💥💞💞欢迎来到本博客❤️❤️💥💥🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密…...
Leetcode.1247 交换字符使得字符串相同
题目链接 Leetcode.1247 交换字符使得字符串相同 Rating : 1597 题目描述 有两个长度相同的字符串 s1和 s2,且它们其中 只含有 字符 "x"和 "y",你需要通过「交换字符」的方式使这两个字符串相同。 每次「交换字符」的时…...
python语音识别whisper
一、背景 最近想提取一些视频的字幕,语音文案,研究了一波 二、whisper语音识别 Whisper 是一种通用的语音识别模型。它在不同音频的大型数据集上进行训练,也是一个多任务模型,可以执行多语言语音识别以及语音翻译和语言识别。 …...
Prometheus -- 浅谈Exporter
Prometheus系统 – Exporter原理 为什么我们需要Exporter? 广义上讲所有可以向Prometheus提供监控样本数据的程序都可以被称为一个Exporter。而Exporter的一个实例称为target,如下所示,Prometheus通过轮询的方式定期从这些target中获取样本…...
如何确定RocketMQ中消费者的线程大小
背景 随着物联网行业的发展、智能设备数量越来越多,随着设备活跃量过大,常常存在一些高并发的请求,形成了流量尖峰,过多的请求会压垮服务器,影响其他服务运行。因此,为了保护云端服务,需要对请求…...
OpenAPI SDK组件之Spring Aop源码拓展
Spring Aop 看这个分享的应该都用过Spring Aop,这里就不再过多介绍了它是什么了。 我抽取了Spring Aop的部分源码,通过它实现请求参数可变拦截,同时apisdk离开Spring框架,仍然可以正常运行。 讲拦截也好,通知也罢&a…...
蓝桥杯C/C++VIP试题每日一练之龟兔赛跑预测
💛作者主页:静Yu 🧡简介:CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家,前端知识交流社区创建者 💛社区地址:前端知识交流社区 🧡博主的个人博客:静Yu的个人博客…...
为你的Vue2.x老项目安装Vite发动机吧
天下苦webpack久矣,相信作为前端开发者一定经历过在项目迭代时间较长的时候经历漫长等待的这一过程,每一次保存都会浪费掉大量时间,这是webpack这种机制所带来的问题。 于是,尤大为我们带来了新一代前端构建工具:vite…...
ZCMU--5012: 铺设道路(差分思路)
Description 春春是一名道路工程师,负责铺设一条长度为 n 的道路。 铺设道路的主要工作是填平下陷的地表。 整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di。 春春每天可以选择一段连续区间 [L,R]&…...
算法模板总结(自用)
算法模板总结滑动窗口双指针算法数组相关合并两个有序数组左右指针技巧快慢指针技巧字符串相关左右指针反转字符串问题快慢指针替换空格字符问题链表相关快慢双指针删除链表的倒数第N个节点链表相交环形链表链表操作几数之和两数之和四个数组的四数之和三数之和同一数组中四数之…...
【架构师】零基础到精通——架构发展
博客昵称:架构师Cool 最喜欢的座右铭:一以贯之的努力,不得懈怠的人生。 作者简介:一名Coder,软件设计师/鸿蒙高级工程师认证,在备战高级架构师/系统分析师,欢迎关注小弟! 博主小留言…...
C++(20):三路比较运算符
C20增加了三路比较运算符<>(戏称航天飞机运算符),用于对类的比较运算符进行统一的设计。有两种使用方式:默认比较对于某些类,如果按照其成员逐一比较即可决定比较运算符的值,那么可以使用默认的三路运…...
MySQL workbench 字符集、字符序的概念与联系
在数据的存储上,MySQL提供了不同的字符集支持。而在数据的对比操作上,则提供了不同的字符序支持。 MySQL提供了不同级别的设置,包括server级、database级、table级、column级,可以提供非常精准的设置。 什么是字符集、字符序&am…...
DBA之路---数据库启动与关闭过程
DBA之路—数据库启动与关闭过程 1、启动过程 oracle启动的四个状态 shutdown、就是数据库关闭状态。 nomount模式 #启动instance ,读取参数文件、分配sga空间启动后台进程,打开alter日志和其他trace文件startup nomount #该模式下只会创建实例并不加…...
Shell文件包含
和其他语言一样,Shell 也可以包含外部脚本。这样可以很方便的封装一些公用的代码作为一个独立的文件。 一、语法格式 Shell 文件包含的语法格式如下: . filename # 注意点号(.)和文件名中间有一空格 或 source filename 在当前bash环境下读取并执行file…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
