시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

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.

입력

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

출력

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.

예제 입력 1

abcefgabc

예제 출력 1

abc

예제 입력 2

abcbabcba

예제 출력 2

abcba

예제 입력 3

aaaa

예제 출력 3

aaa

예제 입력 4

bbcaadbbeaa

예제 출력 4

aa