P3693. 最大重复子串

题目描述

一个字符串的重复次数$R$定义为：该字符串可以被分割成$R$个完全相同的连续子串的最大数目。例如：

• 字符串 $"ababab"$ 的重复次数是$3$（因为它可以分割为$3$个 $"ab"$）
• 字符串 $"ababa"$ 的重复次数是$1$（因为它无法分割为多个相同的连续子串）。

给定一个仅包含小写字母的字符串，请找出其中重复次数最大的子串。

输入格式

输入包含多个测试用例。每个测试用例占一行，给出一个非空的小写字母字符串，长度不超过$100,000$。
最后一个测试用例后是一个单独的 # 表示输入结束。

输出格式

对于每个测试用例，输出一行，格式为 Case X: Y，其中：

• $X$ 是测试用例编号（从$1$开始）
• $Y$ 是满足条件的子串（如果有多个解，输出字典序最小的那个）。

样例输入

ccabababc
daabbccaa
#

样例输出

Case 1: ababab
Case 2: aa

题目来源

2008年亚洲合肥赛区网络赛（USTC主办）

关键点说明

1. 重复次数$R$的数学定义：
   若字符串$S$可表示为$S = T^R$（即子串$T$重复$R$次），则$R$的最大值即为所求。
2. 字典序最小：当存在多个子串的$R$相同时，选择字母序最小的那个（例如 $"aa" < "ab"$）。
3. 高效算法需求：因字符串长度可达$10^5$，暴力解法（$O(n^3)$）不可行，需使用后缀数组或$O(n \log n)$的优化算法。