가장 긴 반복 부분 문자열

시간 제한2초메모리 제한512 MB

요약

겹쳐도 되는 두 번 이상 등장하는 부분 문자열 중 가장 긴 것을 찾습니다. 길이가 같으면 사전순으로 가장 앞서는 것을 출력합니다.

문제

알파벳 소문자로만 이루어진 문자열이 주어진다. 이 문자열에서 두 번 이상 나타나는 부분 문자열 중 가장 긴 것을 찾는다. 두 번 나타나는 위치는 서로 겹쳐도 된다.

한 줄에 알파벳 소문자로 이루어진 문자열이 주어진다. 문자열의 길이는 1보다 크고 $10^5$ 이하다. 적어도 한 글자는 두 번 이상 나타난다.

두 번 이상 나타나는 부분 문자열 중 가장 긴 것을 한 줄에 출력한다. 가장 긴 반복 부분 문자열이 여러 개라면, 그중 사전순으로 가장 앞서는 것을 출력한다.