BOJ 10692 Hamzawy

문제 링크:

문제 내용

영어 소문자로 이루어진 문자열 $S$가 주어집니다. $S$의 부분 문자열 $s$ 중에서 다음을 충족하는 것 중 가장 긴 것을 찾아 출력하세요.

• $s$는 $S$의 prefix이고, suffix이면서, 내부의 부분 문자열입니다. 세 개의 $s$의 등장 위치는 서로 겹치지 않습니다.

입력

첫 번째 줄에는 테스트 케이스의 개수 $T$가 주어집니다. ($1 \le T \le 100$)

각 테스트 케이스에 대해 문자열 $S$가 주어집니다. ($1 \le |S| \le 10000$, 문자열의 길이의 총합 $\le 200\;000$, 테스트 케이스가 약함)

출력

각 테스트 케이스에 대해, Case {테스트 케이스 번호}: {정답 문자열}의 형식으로 출력합니다. 문제의 조건을 충족하는 부분 문자열 $s$가 존재하지 않을 경우, 정답 문자열 대신 -1을 출력합니다.

문제 풀이