어떤 수열에서 0개 이상의 원소를 삭제해서 얻을 수 있는 수열을 그 수열의 부분수열이라 한다.

예를 들어, aab는 X = ababca의 부분수열이지만, Y = cbabba의 부분수열은 아니다.

두 개의 수열이 주어졌을 때, 두 수열에 공통으로 나타나는 부분수열을 두 수열의 공통부분수열이라 한다.

예를 들어, 위 두 수열 X와 Y가 주어졌을 때, baa는 X와 Y의 공통부분수열이지만,

aab는 X와 Y의 공통부분수열이 아니다.

두 수열 X와 Y의 공통부분수열 W가 주어졌을 때, W가 확장 가능하지 아닌지 판별하려고 한다.

W의 한 위치에 어떤 원소를 추가하여 더 긴 공통부분 수열을 만들 수 있으면 W는 확장 가능하고,

그렇지 않으면 W는 확장 불가능하다고 정의한다.

예를 들어, 위의 X와 Y가 주어졌을 때, 공통부분수열 baa는 baba로 확장 가능하다.

하지만, 공통부분수열 ca는 더 이상 확장할 수 없다.

두 수열 X, Y와 두 수열의 공통부분수열 W가 주어졌을 때, W가 확장 가능하지 불가능하지 판별하는 프로그램을 작성하라.

공통 부분 수열 확장 timer 1초 memory 512MB

공통 부분 수열 확장 1초 512MB