공통 부분 수열

면접 대비

시간 제한1초메모리 제한128 MB

요약

주어진 두 문자열의 최장 공통 부분 수열 길이를 여러 테스트 케이스에 대해 구합니다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 문자열
정답자: 아직 제출이 없습니다

문제

주어진 수열의 부분 수열이란, 그 수열에서 원소를 $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$ 을 넘지 않는다. 입력은 항상 올바른 형식으로 주어진다.

출력

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

예제1

예제 1

입력

abcfbc abfcab
programming contest
abcd mnp

예상 출력

4
2
0