역공통초문자열

문자열 집합 S = {S1, S2, ..., Sn}가 주어졌을 때, S의 공통초문자열 R은 S에 속한 모든 문자열이 R의 부분문자열로 나타나는 문자열이다. 예를 들어 S가 {"abb", "baab", "bbc"}라면, S의 공통초문자열 R 중 하나는 길이가 10인 "abbbaabbbc"이다. S에 속한 모든 문자열이 R에서 부분문자열로 나타난다는 점에 주목하자. 확인해 보면 "abb"는 "[abb]baabbbc"에서, "baab"는 "abb[baab]bbc"에서, "bbc"는 "abbbaab[bbc]"에서 나타난다. 문자열 "abbbaabbbc" 역시 S의 공통초문자열이다. 직접 확인해 보자.

가능한 모든 공통초문자열 중에서 보통 가장 짧은 공통초문자열이 더 흥미롭다. 이 문제는 희소 행렬 압축, DNA 염기서열 분석 등 여러 실제 응용을 가진다. 위 예에서 가장 짧은 공통초문자열은 길이가 6인 "baabbc"이다. 확인해 보면 "aab"는 "b[aab]bc"에서, "baab"는 "[baab]bc"에서, "bbc"는 "baa[bbc]"에서 나타난다.

아쉽게도 가장 짧은 공통초문자열을 찾는 문제는 NP-난해로 알려져 있다. 즉, 지금까지 이 문제를 다항 시간에 푸는 알고리즘은 알려지지 않았다.

가장 짧은 공통초문자열을 찾는 문제의 역문제는 다음과 같다. 문자열 R이 주어졌을 때, R이 S의 가장 짧은 공통초문자열이 되는 문자열 집합 S를 찾는 것이다. 물론 이 역문제는 아주 쉽고 자명하다. 집합 S는 R과 같은 문자열 하나만 포함하면 된다. 문자열은 자기 자신의 부분문자열이기도 하다는 점을 기억하자.

이제 더 어려운 문제를 풀어 보자. 문자열 R이 주어졌을 때, R에서 부분문자열로 나타나지 않는 문자열 중 사전순(알파벳순)으로 가장 작은 문자열을 찾아야 한다. 문제를 단순화하기 위해 문자열은 소문자 알파벳(a-z)만으로 이루어진 비어 있지 않은 수열로 정의한다. 예를 들어 R이 "icpc"라면, R에서 부분문자열로 나타나지 않는 사전순으로 가장 작은 문자열은 "a"이다.

문자열 S = S1S2S3...가 문자열 T = T1T2T3...보다 사전순으로 작다는 것은 다음 중 하나가 성립한다는 뜻이다.

• |S| < |T|이고 모든 1 ≤ i ≤ |S|에 대해 Si = Ti이다.
• 어떤 i에 대해 Si < Ti이고 모든 1 ≤ j < i에 대해 Sj = Tj이다.

첫째 줄에 길이가 1 이상 1000 이하인 문자열이 주어진다. 주어지는 문자열은 소문자 알파벳(a-z)만으로 이루어진다.

입력 문자열의 부분문자열이 아닌 문자열 중 사전순으로 가장 작은 문자열을 한 줄에 출력한다. 출력 문자열은 소문자 알파벳만으로 이루어져야 한다.