단짝 문자열
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
Coder's High 2013 문제를 만들던 현종이는 두 번 이상 반복되는 문자열 쌍 찾기를 문제로 낼까 고민하고 있습니다. 하지만 이런 단순한 문제는 Coder's High 2013 참가자에게는 너무 쉬울 것 같아서, 문제를 적당히 변형하기로 했습니다. 이름하여 “가장 긴 단짝 문자열 쌍 찾기”!!
길이가 2L+1인 두 문자열 S와 T가 아래 세 가지 조건을 모두 만족하면, 이 두 문자열을 “단짝 문자열 쌍”이라고 부릅니다. (L >= 1)
- 각 문자열의 가운데 문자를 중심으로 길이가 L인 왼쪽 부분 문자열이 서로 일치한다.
- 각 문자열의 가운데 문자를 중심으로 길이가 L인 오른쪽 부분 문자열이 서로 일치한다.
- 각 문자열의 가운데 문자가 서로 다르다.
예를 들어, “aabcc”와 “aadcc”는 왼쪽 부분 문자열이 “aa”로 일치하고, 오른쪽 부분 문자열도 “cc”로 일치하고, 가운데 문자는 각각 “b”와 “d”로 서로 다릅니다. 위 세 가지 조건을 모두 만족하므로 이 두 문자열은 “단짝 문자열 쌍”입니다.
입력으로 문자열이 하나 주어지면, 이 문자열의 부분 문자열 중 가장 긴 단짝 문자열 쌍을 찾으세요. 이 문자열 쌍은 입력으로 주어진 문자열 내에서 겹치는 부분이 존재할 수도 있습니다. 같은 길이인 단짝 문자열 쌍이 여러가지 있다면, 문자열 쌍을 이어 붙인 문자열이 사전 순으로 가장 앞선 쌍을 고릅니다.
예를 들어, 입력으로 주어진 문자열이 “aadaacaabaa”라면, “aadaa” “aacaa” “aabaa” 세 부분 문자열이 모두 가장 긴 단짝 문자열 쌍이 될 수 있습니다. 한 쌍을 골라 이어 붙였을 때, 사전 순으로 가장 앞선 문자열은 “aabaaaacaa”이므로, “aabaa”와 “aacaa”를 순서대로 출력하면 됩니다.
입력
입력의 첫 줄에는 테스트 케이스의 수 T가 주어집니다. 각 테스트 케이스로 하나의 문자열이 한 줄에 주어집니다. 이 문자열은 길이가 5 이상 2000 이하이고, 전부 알파벳 소문자로 구성되어 있습니다.
출력
각 테스트 케이스마다 한 줄에 가장 긴 단짝 문자열 쌍을 출력합니다. 같은 길이인 단짝 문자열 쌍이 여러가지 있다면, 문자열 쌍을 이어 붙인 문자열이 사전 순으로 가장 앞선 쌍을 출력합니다. 두 문자열 중 사전순으로 더 앞선 문자열을 항상 왼쪽에 출력합니다. 단짝 문자열이 존재하지 않는 경우, “lonely island”라고 출력합니다.
예제 입력
2 aadaacaabaa aabaabac
예제 출력
aabaa aacaa lonely island
노트
