Mid-Central USA Programming Contest 2018

Start

2018-11-03 17:30 UTC

Mid-Central USA Programming Contest 2018

End

2018-11-03 22:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -45 days 4:23:00

Time elapsed

5:00:00

Time remaining

0:00:00

Problem K
Repeated Substrings

Given an input string composed solely of lowercase English letters, find the longest substring that occurs more than once in the input string. The two occurrences are allowed to partially overlap.

Input

The input is a single line containing a string of lowercase letters. The string contains more than one character, but no more than $10^5$. At least one letter will appear at least twice.

Output

Print a single line of output: the longest substring that occurs more than once in the input string. If there are multiple longest repeated substrings, print the one the would come first when the longest substrings are sorted in lexicographical (alphabetical) order.

Sample Input 1 Sample Output 1
abcefgabc
abc
Sample Input 2 Sample Output 2
abcbabcba
abcba
Sample Input 3 Sample Output 3
aaaa
aaa
Sample Input 4 Sample Output 4
bbcaadbbeaa
aa