한글 LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때 두 수열 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

부분 수열은 원래 수열에서 0개 이상의 원소를 지우고 남은 원소의 순서를 그대로 둔 수열이다. 예를 들어 "감자전"과 "전감자튀김"의 LCS는 "감자"이고, "고양이"와 "고등어양념"의 LCS는 "고양"이다.

한글 문자열 두 개가 주어지면 LCS의 길이를 구하는 프로그램을 작성하시오.

첫째 줄과 둘째 줄에 문자열이 하나씩 주어진다. 각 문자열의 길이는 1글자 이상 1000글자 이하이고, 유니코드 U+AC00(가)부터 U+D7A3(힣)까지의 한글 음절로만 이루어져 있으며, UTF-8로 인코딩되어 있다.

첫째 줄에 두 문자열의 LCS의 길이를 글자 수로 출력한다.