최장 공통 부분서열 timer 1초 memory 64MB

2개의 문자열이 입력 될 경우 두 문자열의 최장공통부분 서열의 길이를 출력하는 프로그램을 작성하라.

부분 서열이란, 원래 문자열에서 임의적으로 몇 개의 문자를 제거하여 순서에 맞춰 빈칸 없이 합쳤을 때 만들 수 있는 문자열들을 말한다. 

길이가 0인 문자열이나, 문자열 자기 자신도 부분 서열에 포함된다.

공통 부분 서열이란 문자열 집합 내에서 공통으로 존재하는 부분 서열을 뜻한다. 

예를 들어, 다음과 같이 두개의 문자열이 주어진다고 하자.

abcdgh 

aedfhr

위 두개의 수열의 최장공통부분서열은 adh 이고 길이는 3 이다.​