최장 공통 부분 수열 복원

두 수열이 주어졌을 때 양쪽 모두의 부분 수열이 되는 것 중 가장 긴 것을 최장 공통 부분 수열(LCS, Longest Common Subsequence)이라고 한다. 부분 수열은 원래 수열에서 원소를 0개 이상 지우고 남은 원소의 순서를 그대로 둔 수열이다.

예를 들어 ACAYKP와 CAPCAK의 최장 공통 부분 수열은 길이가 4이고, ACAK가 그중 하나다.

두 문자열의 최장 공통 부분 수열의 길이를 구하고, 길이가 최대인 공통 부분 수열이 여럿이면 사전순으로 가장 앞서는 것을 구한다.

첫째 줄과 둘째 줄에 문자열이 하나씩 주어진다. 두 문자열은 알파벳 대문자로만 이루어지며, 길이는 각각 최대 1000이다.

첫째 줄에 최장 공통 부분 수열의 길이를 출력한다. 길이가 1 이상이면 둘째 줄에 최장 공통 부분 수열을 출력한다. 길이가 최대인 공통 부분 수열이 여럿이면 그중 사전순으로 가장 앞서는 것을 출력한다. 길이가 0이면 둘째 줄은 출력하지 않는다.