# 描述

The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of ababab is $3$ and ababa is $1$.

Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.

## Input

The input consists of multiple test cases. Each test case contains exactly one line, which gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than $100,000$.

The last test case is followed by a line containing a #.

## Output

For each test case, print a line containing the test case number( beginning with $1$) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.

# 思路

• 罗穗骞的论文题。这类问题先求出原串的后缀数组和高度数组，然后在高度数组上面做事情。
• 先枚举循环节的长度$l$，然后求$suffix[i]$和$suffix[i+l]$的LCP，记为$k$（即向后匹配），出现次数则为$k/l+1$。但是这存在一个问题，论文中的图也反映了这一点，我们在求LCP的时候是向后匹配的，但是可能存在向前的匹配使得循环次数再多一次，所以我们还要再去向前匹配一下。
• 由于要输出字典序最小的解，所以要把循环节长度记下来。最后只要在sa数组中跑一遍，因为sa数组本身就是按字典序的，所以第一个符合条件的就是字典序最小的了。

0%