여우 나라의 앨리스

디폭시레나르드핵산(줄여서 DNA)과 레나르드핵산(줄여서 RNA)은 생물이 지닌 비슷한 유기 분자다. 두 분자는 모두 26가지 염기가 늘어선 서열이고, 염기 한 종류를 a부터 z까지의 소문자 한 글자로 나타내면 서열은 문자열이 된다. DNA와 RNA는 염기가 결합하는 방식만 다르다.

2323년에 푹스 교수는 특정 부분문자열을 포함한 DNA가 촉매로 작용해 어떤 화학 반응을 빠르게 한다는 사실을 발견했다. 또 서열이 긴 DNA일수록 반응을 더 많이 빠르게 한다는 사실도 알아냈다. 예를 들어 fox를 포함한 DNA는 질소 산화물(NOx)의 용해를 촉진하는 촉매다. redfox와 cutefoxes가 그런 DNA이고, cutefoxes가 redfox보다 반응을 더 많이 빠르게 한다. foooox는 fox를 부분문자열로 포함하지 않으므로 촉매가 되지 못한다.

DNA는 글로리오사 같은 식물에서 쉽게 추출한다. 그러나 추출한 분자는 거의 모두 서열이 서로 달라서, 촉매로 작용하는 분자는 아주 조금밖에 얻지 못한다. 그래서 많은 과학자가 원하는 분자를 얻는 방법을 찾아 왔다.

2369년에 후 교수는 마침내 다음 과정을 발견했다.

1. DNA 두 개 X와 Y를 준비한다.
2. DNA X와 Y의 서열을 그대로 복사해 RNA X'과 Y'을 만든다.
3. 약품으로 X'에서 염기를 0개 이상 삭제해 RNA X''을 얻는다.
4. 마찬가지로 Y'에서 염기를 0개 이상 삭제해, X''과 서열이 같은 RNA Y''을 얻는다.
5. 두 RNA X''과 Y''에서 X'', Y''과 서열이 같은 DNA Z를 얻는다.

그림 1: 새로운 DNA 생성 방법

핵심은 RNA를 거치는 것이다. DNA에서 특정 염기를 삭제하기는 어렵지만 RNA에서는 비교적 쉽다. 한편 RNA는 DNA보다 불안정하고, 생물에서 RNA를 직접 얻는 방법은 알려져 있지 않다. 그래서 DNA에서 RNA를 얻는다.

앨리스는 Tail Environmental Natural Catalyst Organization의 연구원이다. 지금 앨리스는 후 교수의 방법을 여러 DNA 쌍에 적용해 특정 부분문자열을 포함한 DNA를 만들어야 한다. 긴 DNA일수록 좋으므로 얻을 수 있는 가장 긴 DNA를 알아내는 방법이 필요하다. 그래서 앨리스가 당신에게 도움을 청했다.

주어진 DNA 쌍 X와 Y로 생성할 수 있으면서 주어진 부분문자열 C를 포함하는, 가장 긴 DNA의 서열을 출력하는 프로그램을 작성하라.

입력은 여러 데이터 집합으로 이루어진다. 각 데이터 집합은 세 줄이다. 첫째 줄과 둘째 줄에 서열 X와 Y가 주어지고, 셋째 줄에 부분문자열 C가 주어진다. 각 서열과 부분문자열은 a부터 z까지의 소문자만 포함하고, 길이는 1 이상 1600 이하다.

마지막 데이터 집합 다음 줄에는 * 한 글자만 있는 줄이 오고, 거기서 입력이 끝난다.

각 데이터 집합마다 가장 긴 서열을 한 줄에 출력한다. 가장 긴 서열이 둘 이상이면 그중 사전순으로 가장 작은 것을 출력한다. C를 포함하는 DNA를 어떤 방법으로도 얻을 수 없으면 대신 Impossible을 출력한다.

길이가 같은 두 문자열 s와 t에서, 처음으로 서로 다른 위치의 글자가 s 쪽이 더 작으면 s가 t보다 사전순으로 작다.