부분 수열(subsequence)이란, 원래 수열에서 몇 개의 원소를 골라 순서를 유지한 채로 이어 붙인 수열을 말한다.

예를 들어, “ICPC”는 “MICROPROCESSOR”의 부분 수열이다.

공통 부분 수열이란, 두 수열 모두의 부분 수열이 되는 수열을 말한다.

가장 긴 공통 부분 수열을 구하는 문제는 유명하다.

이 문제에서는 가장 짧은 공통 안부분수열을 구한다.

0과 1로만 이루어진 두 문자열 A, B가 주어졌을 때, 0과 1로만 이루어져 있으면서,

A의 부분수열이 아니고 B의 부분수열도 아닌 문자열 중 가장 짧은 것을 출력하여라.

가장 짧은 것이 여러 개일 경우 사전순으로 먼저 나오는 문자열을 출력한다.

가장 짧은 공통 안부분수열 timer 2s memory 512MB

가장 짧은 공통 안부분수열 2s 512MB