공통 부분 수열

주어진 수열의 부분 수열이란, 그 수열에서 원소를 $0$개 이상 골라 빼고 남은 수열을 말한다. 정확히 말하면, 수열 $X = \langle x_1, x_2, \ldots, x_m \rangle$이 주어졌을 때, 수열 $Z = \langle z_1, z_2, \ldots, z_k \rangle$이 $X$의 부분 수열이라는 것은, 모든 $j = 1, 2, \ldots, k$에 대해 $x_{i_j} = z_j$를 만족하는 강한 증가 인덱스 수열 $\langle i_1, i_2, \ldots, i_k \rangle$이 존재한다는 뜻이다. 예를 들어 $Z = \langle a, b, f, c \rangle$은 인덱스 수열 $\langle 1, 2, 4, 6 \rangle$을 통해 $X = \langle a, b, c, f, b, c \rangle$의 부분 수열이 된다.

두 수열 $X$와 $Y$가 주어질 때, $X$와 $Y$의 최장 공통 부분 수열(둘 모두의 부분 수열이 되는 수열)의 길이를 구하여라.

입력은 여러 개의 데이터 집합으로 이루어져 있으며 파일의 끝까지 계속된다. 각 데이터 집합은 각각 하나의 수열을 나타내는 두 개의 문자열로 이루어진다. 한 데이터 집합의 두 문자열, 그리고 연속한 데이터 집합들은 임의의 개수의 공백 문자(스페이스, 탭, 줄바꿈)로 구분된다. 각 문자열의 길이는 $200$을 넘지 않는다. 입력은 항상 올바른 형식으로 주어진다.

각 데이터 집합에 대해, 두 수열의 최장 공통 부분 수열의 길이를 한 줄에 하나씩 출력한다.