카멜레온 부분 문자열

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

요약

문자열 S가 주어질 때, S의 접두사이면서 접미사이고 S의 안쪽에도 나타나는 가장 긴 부분 문자열을 구한다.

문제

문자열 $S$ 의 부분 문자열 $T$ 가 다음 세 조건을 모두 만족하면 $T$ 를 카멜레온 부분 문자열이라고 한다.

$T$ 는 $S$ 의 접두사이다.
$T$ 는 $S$ 의 접미사이다.
$S$ 안에서 $T$ 가 위의 두 자리가 아닌 자리에도 등장한다. 즉 $S$ 의 첫 문자에서 시작하지도 않고 $S$ 의 마지막 문자에서 끝나지도 않는 $T$ 의 등장이 하나 이상 있다.

세 등장은 서로 겹쳐도 된다.

예를 들어 $S =$ fixprefixsuffix이면 fix는 카멜레온 부분 문자열이다. fix는 $S$ 의 접두사이자 접미사이고, 7번째 문자에서 시작하는 등장도 있다.

문자열 $S$ 가 주어지면 가장 긴 카멜레온 부분 문자열을 구한다.

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 는 알파벳 소문자로만 이루어지고, 길이는 $1$ 이상 $10^6$ 이하이다.

가장 긴 카멜레온 부분 문자열을 첫째 줄에 출력한다. 카멜레온 부분 문자열은 $S$ 의 접두사이므로 길이가 정해지면 문자열도 하나로 정해지고, 답은 유일하다. 카멜레온 부분 문자열이 없으면 -1을 출력한다.