《蓝桥杯每日一题》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…...
19c补丁后oracle属主变化,导致不能识别磁盘组
补丁后服务器重启,数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后,存在与用户组权限相关的问题。具体表现为,Oracle 实例的运行用户(oracle)和集…...
Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包
文章目录 现象:mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时,可能是因为以下几个原因:1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...
