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
|