10080 가장 긴 공통 부분수열 Gold V

문제

두 문자열이 주어졌을 때, 두 문자열의 가장 긴 공통 부분수열(LCS)의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄과 둘째 줄에 문자열이 주어진다. 각 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 1 이상 1,000 이하이다.

출력

LCS의 길이를 출력한다.

ACAYKP
CAPCAK

4