cho.sh

DNA 문자열

DNA 문자열 S가 주어질 때, S의 연속 부분 문자열로 나타나지 않는 가장 짧은 A, C, G, T 문자열을 찾고, 여러 개면 사전순으로 가장 앞선 것을 출력한다.

보통5문자열문자열 매칭완전 탐색아직 제출이 없습니다시간 제한2초메모리 제한512 MB

문제

DNA는 A, C, G, T로만 이루어진 문자열이다.

영선이는 인간 유전자를 연구하려고 생물학자 효빈이를 고용했다. 효빈이가 연구하는 DNA는 문자열 SS이다. 효빈이는 SS 안에 연속으로 등장하지 않는 가장 짧은 DNA 문자열을 찾으려고 한다.

길이가 가장 짧은 답이 여러 개일 수 있다. 그런 경우에는 사전 순으로 가장 앞선 문자열 하나만 정답으로 인정한다. 문자의 크기 순서는 A, C, G, T이다.

예를 들어 SS = "AGGTCTA"를 보자. 길이가 1인 문자열 A, C, G, T는 모두 SS에 등장하므로 답의 길이는 2 이상이다. 길이가 2인 문자열 중 "AA"는 SS에 등장하지 않고, 사전 순으로 "AA"보다 앞선 길이 2짜리 문자열은 없으므로 답은 "AA"이다. "AG"는 SS에 등장하므로 답이 될 수 없고, "AAA"는 길이가 2인 답이 있으므로 답이 될 수 없다.

SS가 주어졌을 때 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 SS가 주어진다. SS는 A, C, G, T로만 이루어져 있고, 길이는 1 이상 2,000 이하이다.

출력

첫째 줄에 SS 안에 연속으로 등장하지 않는 가장 짧은 DNA 문자열을 출력한다. 그런 문자열이 여러 개면 사전 순으로 가장 앞선 것을 출력한다. 문자의 크기 순서는 A, C, G, T이다.