시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 88 41 29 49.153%

문제

문자열 S의 부분 문자열 T 중에서, 접두사(Prefix)도 될 수 있고, 접미사(Prefix)도 될 수 있고, 두 경우에 모두 해당되지 않는 T를 카멜레온 부분 문자열이라고 한다.

문자열 S가 주어졌을 때, 카멜레온 부분 문자열을 구하는 프로그램을 작성하시오.

예를 들어, S = "fixprefixsuffix"와 같은 경우에는 "fix"는 접두사, 접미사도 되고, 두 경우가 아닌 부분 문자열로도 등장한다.

입력

첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져있으며, 길이는 106을 넘지 않는 자연수이다.

출력

가능한 카멜레온 부분 문자열 T 중에서 길이가 가장 긴 것을 출력한다. 만약, T가 존재하지 않으면 -1을 출력한다.

예제 입력

fixprefixsuffix

예제 출력

fix

예제 입력 2

abcdabc

예제 출력 2

-1

예제 입력 3

qwertyqwertyqwerty

예제 출력 3

qwerty

예제 입력 4

papapapap

예제 출력 4

papap

힌트

출처