문제

수열 $X$에서 원소 몇 개를 골라 원래의 순서를 유지한 채 이어 붙여 만든 수열을 $X$의 부분 수열이라고 한다. 예를 들어 문자열 ACAYKP의 부분 수열로는 AAK, CYP, ACAYKP 등이 있고, KAY는 부분 수열이 아니다.

알파벳 대문자로 이루어진 두 문자열 $A$와 $B$가 주어진다. $A$의 부분 수열이면서 동시에 $B$의 부분 수열인 문자열을 두 문자열의 공통 부분 수열이라고 하며, 그중 가장 긴 것을 최장 공통 부분 수열(LCS, Longest Common Subsequence)이라고 한다.

두 문자열 $A$와 $B$가 주어졌을 때, 최장 공통 부분 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 $A$가, 둘째 줄에 문자열 $B$가 주어진다. 두 문자열은 모두 알파벳 대문자로 이루어져 있으며, 길이는 각각 $1$ 이상 $1\,000$ 이하이다.

출력

첫째 줄에 두 문자열의 최장 공통 부분 수열의 길이를 출력한다.

예제 입력 1

ACAYKP
CAPCAK

예제 출력 1

4

예제 입력 2

ABCBDAB
BDCAB

예제 출력 2

4

노트

이 문제가 왜 중요할까? LCS 알고리즘은 다양한 곳에서 사용되고 있다. 대표적인 예시는 아래와 같다.

1. Git을 비롯한 버전 관리 시스템(VCS)의 코드 비교 도구
2. 생물정보학에서의 DNA 염기서열이나 단백질 아마노산 서열의 비교 (질병 예측, 치료제 개발 등)
3. LLM 모델의 평가 지표 (ROUGE-L)