DNA 유사도

시간 제한

1초

메모리 제한

128 MB

문제

모든 생물의 DNA 서열은 A, C, G, T 네 문자로 이루어진다.

두 DNA 서열의 유사도는 두 서열의 여러 위치에 공백을 삽입해 길이를 같게 만든 뒤 계산한다.

같은 위치에 공백이 아닌 같은 문자가 있으면 3점을 더한다.
같은 위치의 문자가 서로 다르거나, 둘 중 하나가 공백이면 2점을 뺀다.

가능한 모든 공백 삽입 방법 중 얻을 수 있는 최대 점수가 두 서열의 유사도이다. 예를 들어 AGTCAG와 ATGTG는 다음과 같이 정렬할 수 있다.

이 정렬의 점수는 3이다. 다른 정렬은 다음과 같다.

이 정렬의 점수는 6이다. 따라서 두 전체 서열 AGTCAG와 ATGTG의 유사도는 6이다.

DNA 서열의 부분 서열은 원래 서열에서 연속한 구간을 잘라 얻은 서열이다. 예를 들어 AGTCAG에서 첫 번째부터 세 번째 문자까지 자르면 AGT이고, 두 번째부터 다섯 번째 문자까지 자르면 GTCA이다.

두 DNA 서열에서 서로 같은 정보를 담고 있을 가능성이 큰 구간을 찾기 위해, 두 서열에서 각각 하나의 부분 서열을 골라 그 유사도가 최대가 되는 쌍을 찾으려 한다. 예를 들어 AGTCAG에서 AGT를, ATGTG에서 ATGT를 고르면 다음 정렬로 점수 7을 얻는다.

두 DNA 서열이 주어질 때, 유사도가 최대인 부분 서열 쌍의 유사도와 그 부분 서열 쌍을 출력하시오.

입력

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

각 DNA 서열의 길이는 1000 이하이며, 서열을 이루는 문자 사이에는 공백이 없다. 두 DNA 서열은 공통 문자를 적어도 하나 가진다.

출력

첫째 줄에 두 DNA 서열의 부분 서열 쌍 중 유사도가 최대인 쌍의 유사도를 출력한다.

둘째 줄에는 첫 번째 DNA 서열에서 고른 부분 서열을 출력하고, 셋째 줄에는 두 번째 DNA 서열에서 고른 부분 서열을 출력한다. 유사도가 최대인 부분 서열 쌍이 둘 이상이면 그중 하나만 출력하면 된다.