DNA 유사도

DNA 서열은 A, C, G, T 네 문자로만 이루어진다. 한 서열에서 두 문자의 거리는 두 문자 사이에 놓인 문자의 개수이다. 부분서열은 원래 서열에서 몇 개의 문자를 삭제하여 얻는 서열이다.

정수 K가 0 이상일 때, 어떤 부분서열이 원래 DNA 서열의 K-부분서열이라는 것은 그 부분서열에서 서로 이웃한 두 문자가 원래 서열에서도 서로 떨어진 거리가 모두 K 이하라는 뜻이다. 예를 들어 AGTCAC에서 두 번째 문자 G와 다섯 번째 문자 A 사이에는 T와 C 두 문자가 있으므로, 이 두 문자를 이웃하게 고른 부분서열은 1-부분서열이 될 수 없고 2-부분서열은 될 수 있다.

두 DNA 서열의 최장 공통 K-부분서열은 두 서열 모두에서 K-부분서열로 얻을 수 있는 같은 서열 중 길이가 가장 긴 것을 말한다. 답은 여러 개일 수 있다.

예를 들어 AGTCAC와 GATGAGAC가 주어졌을 때 AGAC와 GTAC는 최장 공통 2-부분서열이다. K = 1일 때 가능한 최장 공통 K-부분서열은 AGC, GTA, ATA이고, 이들을 사전순으로 정렬하면 AGC, ATA, GTA이다.

두 DNA 서열과 K가 주어질 때, 사전순으로 가장 앞서는 최장 공통 K-부분서열을 구하시오.

첫째 줄에 정수 K가 주어진다. K는 0 이상 30 이하이다.

둘째 줄에 첫 번째 DNA 서열의 길이가 주어진다. 셋째 줄에 첫 번째 DNA 서열이 주어진다.

넷째 줄에 두 번째 DNA 서열의 길이가 주어진다. 다섯째 줄에 두 번째 DNA 서열이 주어진다.

각 DNA 서열의 길이는 1 이상 1,000 이하이며, 서열을 이루는 문자 사이에는 공백이 없다.

주어진 두 DNA 서열의 최장 공통 K-부분서열을 출력한다. 답이 여러 개이면 사전순으로 가장 앞서는 서열을 출력한다.