AN. 最短循环节

    传统题 1000ms 256MiB

最短循环节

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

给定一个非空字符串 ss,如果它能由某个非空字符串 tt 连续、完整地重复 kk 次得到(kk 为正整数),即

s=tt⋯t⏟k 个 t,s=\underbrace{tt\cdots t}_{k\text{ 个 }t},

就称 tt 是 ss 的一个循环单元。例如,ababab 可以由 ab 重复 33 次得到,也可以由 ababab 重复 11 次得到。

请求出 ss 的最短循环单元及其长度。每个非空字符串都能由自身重复 11 次得到,因此答案一定存在。

输入格式

输入一行一个字符串 ss(1≤∣s∣≤30001\le |s|\le 3000),ss 仅由小写英文字母 a 到 z 组成。

输出格式

输出一行两个内容:最短循环单元的长度 LL 和最短循环单元 tt,两者之间用一个空格分隔。

最短循环单元一定是 ss 的前缀,因此它是唯一的。不要输出提示文字或其他多余内容。

数据范围

  • 1≤∣s∣≤30001\le |s|\le 3000。
  • ss 仅由小写英文字母 a 到 z 组成。
  • 输入只有一组测试数据。

样例

ababab
2 ab

长度为 11 的循环单元重复后,所有字符都必须相同,所以 ababab 不存在这样的循环单元。ababab 恰好由 ab 完整重复 33 次得到,因此最短循环单元为 ab。

abcab
5 abcab

abcab 的长度为 55。若循环单元比整个字符串短,其长度只能为 11,但字符串中的字符并不全相同。因此最短循环单元只能是 abcab 自身。

说明

虽然 abcab 的前缀 ab 也在末尾出现,但 ab 重复整数次无法恰好得到 abcab。循环单元必须完整重复,末尾不能留下多余字符。

评测器会依次检查输出的长度、循环单元、完整重复条件和最短性;多余输出会被判为错误。

2026级SYUCT-ACM新生第四次训练

未参加
状态
已结束
规则
XCPC
题目
40
开始于
2026-10-30 18:30
结束于
2026-11-16 10:30
持续时间
400 小时
主持人
参赛人数
62