【算法竞赛进阶指南】141.周期 题解 KMP 最小循环节
题目描述
一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab
共有 5 5 5 个前缀,分别是 a
,ab
,aba
,abaa
,abaab
。
我们希望知道一个 N N N 位字符串 S S S 的前缀是否具有循环节。
换言之,对于每一个从头开始的长度为 i i i( i > 1 i>1 i>1)的前缀,是否由重复出现的子串 A A A 组成,即 A A A … A AAA…A AAA…A ( A A A 重复出现 K K K 次, K > 1 K>1 K>1)。
如果存在,请找出最短的循环节对应的 K K K 值(也就是这个前缀串的所有可能重复节中,最大的 K K K 值)。
输入格式
输入包括多组测试数据,每组测试数据包括两行。
第一行输入字符串 S S S 的长度 N N N。
第二行输入字符串 S S S。
输入数据以只包括一个 0 0 0 的行作为结尾。
输出格式
对于每组测试数据,第一行输出 Test case #
和测试数据的编号。
接下来的每一行,输出具有循环节的前缀的长度 i i i 和其对应 K K K,中间用一个空格隔开。
前缀长度需要升序排列。
在每组测试数据的最后输出一个空行。
数据范围
2 ≤ N ≤ 1000000 2 \le N \le 1000000 2≤N≤1000000
输入样例:
3
aaa
4
abcd
12
aabaabaabaab
0
输出样例:
Test case #1
2 2
3 3Test case #2Test case #3
2 2
6 2
9 3
12 4
题意重述
编写一个程序,对于每一个前缀子串 s i s_i si,找出它的最短循环节的重复次数。 s i s_i si 的最短循环节是指连续组合能恰好构成 s i s_i si 的最短的子串。例如,对于字符串 “aabaabaa”,“aab” 不是其最短循环节,因为它无法恰好构成原串。
注意,在以下叙述中,下标从1开始。
算法
通过KMP算法可以求得next数组,对于每一个前缀子串 s i s_i si,其最短循环节的长度就是 i − next [ s i ] i - \text{next}[s_i] i−next[si]。
为什么呢?
首先看图,上下两条线表示同一个字符串,重合的部分表示KMP匹配(前后缀相等的最大长度)。
上面的1就是下面的1(完全相同的部分),而下面的1等于上面的2(前后缀匹配),上面的2等于下面的2,而下面的2等于上面的3…
所以上面的1,2,3,4,5和下面的1,2,3,4,5完全相同。
在不严格要求“恰好”构成时,每一小段都可以视作原串的循环节。然后,我们可以证明,这样的小段就是原串的最短循环节。
那么,如何证明呢?
反证: 假设该小段字符串T不是最短循环节,则原串中必然存在T’作为最短循环节。那么对于T’,可以按照上图的方式,将上下两串划分为一个个由T’组成的部分。
此时矛盾出现:如果可以用更小的T’划分,则根据图示,原串的KMP匹配长度就是 n − len ( T ′ ) n - \text{len}(T') n−len(T′)。这个长度 n − len ( T ′ ) n - \text{len}(T') n−len(T′) 超过了 n − len ( T ) n - \text{len}(T) n−len(T),而 n − len ( T ) n - \text{len}(T) n−len(T) 是原串的最大前后缀匹配长度。所以假设是错误的,也就是说,T确实是最短循环节。
当不严格要求“恰好”构成时, n − len ( T ) = n − next [ n ] n - \text{len}(T) = n - \text{next}[n] n−len(T)=n−next[n] 就是最短循环节的长度。对于每一个前缀子串 s i s_i si,其最短循环节的长度就是 i − next [ i ] i - \text{next}[i] i−next[i]。那么,当我们严格要求恰好构成时,又会是怎样呢?
我们可以证明一个引理,一个字符串的任何循环节(除最短循环节外)都是最短循环节的倍数。也就是说,不存在其他可能的模式使得原串能够恰好由其循环构成。因此,如果原串长度能被 l e n ( T ) len(T) len(T) 整除,则存在最短循环节且为 s [ 1 ∼ l e n ( T ) ] s[1\sim len(T)] s[1∼len(T)],如果不能被整除,则不存在(按题目的要求,不能“恰好”构成就是为不存在)。
引理证明:
反证: 假设原串存在一个子串T’,它不是最短循环节,也不是最短循环节的循环构成(倍数),但是可以循环构成原串。(有点绕)
这就意味着 l e n ( T ′ ) > l e n ( T ) len(T') > len(T) len(T′)>len(T),且 l e n ( T ′ ) len(T') len(T′) 不是 l e n ( T ) len(T) len(T) 的倍数。根据循环节的定义,T 和 T’ 都可以构成原串。即原串可以写为 T T . . . T A TT...TA TT...TA(T出现 m 次)或 T ′ T ′ . . . T ′ B T'T'...T'B T′T′...T′B(T’出现 n 次)。这里的 A 和 B 可能是空串,或者长度不足一个 T 或 T’ 的部分。满足 m × l e n ( T ) = n × l e n ( T ′ ) m \times len(T) = n \times len(T') m×len(T)=n×len(T′)。
于是我们可以找到一个更小的循环节,其长度为d,因为
s j = s j + l e n ( T ) = s j + 2 l e n ( T ) = ⋯ = s j + x l e n ( T ) = s j + x l e n ( T ) − l e n ( T ′ ) = s j + x l e n ( T ) − 2 l e n ( T ′ ) = ⋯ = s j + x l e n ( T ) − y l e n ( T ′ ) = s j + d s_j=s_{j+len(T)}=s_{j+2len(T)}= \cdots =s_{j+xlen(T)}=s_{j+xlen(T)-len(T')}=s_{j+xlen(T)-2len(T')}=\cdots =s_{j+xlen(T)-ylen(T')}=s_{j+d} sj=sj+len(T)=sj+2len(T)=⋯=sj+xlen(T)=sj+xlen(T)−len(T′)=sj+xlen(T)−2len(T′)=⋯=sj+xlen(T)−ylen(T′)=sj+d
此处的 j j j 可以从几乎任意位置开始,只要字符串的长度足够长以支持所描述的周期 (如果不支持,那么表示从j开始的后续部分无法使用T’进行重复构成,这样的情况则不需要讨论。)。
但这与T是最短循环节的假设产生矛盾,假设不成立。故不存在一种循环节使得它既不是最短循环节,也不是最短循环节的倍数。
看明白了,请给我点赞,谢谢(*^▽^*)。
时间复杂度 O ( n ) \mathcal{O}(n) O(n)
KMP+线性扫描, O ( n ) \mathcal{O}(n) O(n)。
C++ 代码
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
char s[N]; int ne[N];int main(){int T = 1;int n;while(scanf("%d", &n), n){printf("Test case #%d\n", T ++);scanf("%s", s + 1);for(int i = 2, j = 0; i <= n; ++ i){while(j && s[i] != s[j + 1]) j = ne[j];if(s[i] == s[j + 1]) j ++;ne[i] = j;}for(int i = 1; i <= n; ++ i){int t = i - ne[i];if(i > t && i % t == 0){ // i>t保证循环节至少出现2次printf("%d %d\n", i, i / t);}}puts("");}
}
相关文章:

【算法竞赛进阶指南】141.周期 题解 KMP 最小循环节
题目描述 一个字符串的前缀是从第一个字符开始的连续若干个字符,例如 abaab 共有 5 5 5 个前缀,分别是 a,ab,aba,abaa,abaab。 我们希望知道一个 N N N 位字符串 S S S 的前缀是否具有循环节。 换言之…...
【Springboot 入门培训 】#19 Spring Boot 组件扫描与bean生命周期
目录 1 什么是组件扫描2 何时使用组件扫描3 扫描整个包basePackages与 includeFilters4 Spring boot 的 Bean 生命周期4.1 生命周期4.2 Bean 生命周期4.3 周期各个阶段 首先,我想先为你介绍一下“Spring”,这是一个开放源代码的设计模式解决方案和轻量级…...
Linux printf 函数输出问题
printf 函数并不会直接将数据输出到屏幕,而是先放到缓冲区中,只有一下三种情况满足,才会输出到屏幕。 1) 缓冲区满 2) 强制刷新缓冲区 fflush 3) 程序结束时 1 #include<stdio.h>2 #include<st…...

皮卡丘Unsafe Fileupload
1.不安全的文件上传漏洞概述 文件上传功能在web应用系统很常见,比如很多网站注册的时候需要上传头像、上传附件等等。当用户点击上传按钮后,后台会对上传的文件进行判断 比如是否是指定的类型、后缀名、大小等等,然后将其按照设计的格式进行…...

最优化简明版(上)
引言 本文简单地介绍一些凸优化(Convex Optimization)的基础知识,可能不会有很多证明推导,目的是能快速应用到机器学习问题上。 凸集 直线与线段 设 x 1 ≠ x 2 x_1 \neq x_2 x1x2为 R n \Bbb R^n Rn空间中的两个点,那么具有下列形…...
MySQL的一些介绍
1. SQL的select语句完整的执行顺序 SQL Select语句完整的执行顺序: 1、from子句组装来自不同数据源的数据; 2、where子句基于指定的条件对记录行进行筛选; 3、group by子句将数据划分为多个分组; 4、使用聚集函数进行计算&am…...

unity发布webGL后无法预览解决
众所周知,unity发布成webgl后是无法直接预览的。因为一般来说浏览器默认都是禁止webgl运行的。 直接说我最后的解决方法:去vscode里下载一个live server ,安装好。 下载vscode地址Visual Studio Code - Code Editing. Redefined 期间试过几种方法都不管…...

Flume和Kafka的组合使用
一.安装Kafka 1.1下载安装包 通过百度网盘分享的文件:复制链接打开「百度网盘APP 即可获取」 链接:https://pan.baidu.com/s/1vC6Di3Pml6k1KMbnK0OE1Q?pwdhuan 提取码:huan 也可以访问官网,下载kafka2.4.0的安装文件 1.2解…...

JSONSQL:使用SQL过滤JSON类型数据(支持多种数据库常用查询、统计、平均值、最大值、最小值、求和语法)...
1. 简介 在开发中,经常需要根据条件过滤大批量的JSON类型数据。如果仅需要过滤这一种类型,将JSON转为List后过滤即可;如果相同的条件既想过滤数据库表中的数据、也想过滤内存中JSON数据,甚至想过滤Elasticsearch中的数据ÿ…...

Linux输入输出重定向
目录 Linux输入输出重定向 Linux中的默认设备 输入输出重定向定义 输入输出重定向操作符 实用形式 标准输入、标准输出、标准错误 输出重定向案例 案例1 --- 输出重定向(覆盖) 案例2 --- 输出重定向(追加) 案例3 --- 错误…...

使用kettle进行数据统计
1.使用kettle设计一个能生成100个取值范围为0到100随机整数的转换。 为了完成该转换,需要使用生成记录控件、生成随机数控件、计算器控件及字段选择控件。控件布局如下图所示 生成记录控件可以在限制框内指定生成记录的个数,具体配置如图所示 生成随机数…...
线程的取消和清理
一、线程的取消 意义:随时杀掉一个线程 int pthread_cancel(pthread_t thread); 注意:线程的取消要有取消点才可以,不是说取消就取消,线程的取消点主要是阻塞的系统调用 二、运行段错误调试 可以使用gdb调试 使用gdb 运行代…...

day8 -- 全文本搜索
brief InnoDB存储引擎从MySQL 5.6开始支持全文本搜索。具体来说,MySQL使用InnoDB存储引擎的全文本搜索功能称为InnoDB全文本搜索(InnoDB Full-Text Search)。InnoDB全文本搜索支持标准的全文本搜索查询语法和多语言分词器,因此可…...
C语言:if-else语句
嗨,今天咱们讲讲C语言控制语句里的条件选择,主要总结下if else语句。 咱们生活里经常会有这样的场景,明天该怎么穿呢,得考虑下具体的天气。如果是晴天,温度还不错,可以穿T恤;如果是阴天…...

C语言---函数
1、函数是什么 学习库函数网站: https://cplusplus.com/reference/http://en.cppreference.comhttp://zh.cppreference.com 我们参考文档,学习几个库函数 2、库函数 3、自定义函数 自定义函数和库函数一样,有函数名,返回值类…...

【JVM】什么是双亲委派机制?
一、为什么会有这种机制? 类加载器将.class类加载到内存中时,为了避免重复加载(确保Class对象的唯一性)以及JVM的安全性,需要使用某一种方式来实现只加载一次,加载过就不能被修改或再次加载。 二、什么是双…...

Vulkan Tutorial 7 纹理贴图
目录 23 图像 图片库 暂存缓冲区 纹理图像 布局转换 将缓冲区复制到图像上 准备纹理图像 传输屏障掩码 清除 24 图像视图和采样器 纹理图像视图 采样器 Anisotropy 设备特征 25 组合图像采样器 更新描述符 纹理坐标系 着色器 23 图像 添加纹理将涉及以下步骤&am…...
LinkedBlockingQueue阻塞队列
➢ LinkedBlockingQueue阻塞队列 LinkedBlockingQueue类图 LinkedBlockingQueue 中也有两个 Node 分别用来存放首尾节点,并且里面有个初始值为 0 的原子变量 count 用来记录队列元素个数,另外里面有两个ReentrantLock的独占锁,分别用来控制…...
面试-Redis 常见问题,后续面试遇到新的在补充
面试-Redis 1.谈谈Redis 缓存穿透,击穿,雪崩及如何避免 缓存穿透:是指大量访问请求在访问一个不存在的key,由于key 不存在,就会去查询数据库,数据库中也不存在该数据,无法将数据存储到redis 中…...

2023年上半年数据库系统工程师上午真题及答案解析
1.计算机中, 系统总线用于( )连接。 A.接口和外设 B.运算器、控制器和寄存器 C.主存及外设部件 D.DMA控制器和中断控制器 2.在由高速缓存、主存和硬盘构成的三级存储体系中,CPU执行指令时需要读取数据,那么DMA控制器和中断CPU发出的数据地…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

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

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装
以下是基于 vant-ui(适配 Vue2 版本 )实现截图中照片上传预览、删除功能,并封装成可复用组件的完整代码,包含样式和逻辑实现,可直接在 Vue2 项目中使用: 1. 封装的图片上传组件 ImageUploader.vue <te…...

华为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…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...

spring Security对RBAC及其ABAC的支持使用
RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型,它将权限分配给角色,再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...