5219 : A20 - 최장 공통 부분 수열 (LCS)
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
문자열 $S$ 와 $T$ 가 주어집니다.
$S$ 와 $T$ 의 공통 부분 수열($S$ 의 부분 수열이면서 $T$ 의 부분 수열인 것) 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하십시오.
단, 문자열의 부분 수열이란 그 문자열에서 순서를 바꾸지 않고 일부 문자를 추출한 것을 의미합니다.
예를 들어, `grain`은 `programming`의 부분 수열입니다 (4, 5, 6, 9, 10번째 문자를 추출).
[제약 조건]
• $1 \le |S| \le 2000$
• $1 \le |T| \le 2000$
• $S, T$ 는 영소문자로 이루어진 문자열입니다.
$S$ 와 $T$ 의 공통 부분 수열($S$ 의 부분 수열이면서 $T$ 의 부분 수열인 것) 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하십시오.
단, 문자열의 부분 수열이란 그 문자열에서 순서를 바꾸지 않고 일부 문자를 추출한 것을 의미합니다.
예를 들어, `grain`은 `programming`의 부분 수열입니다 (4, 5, 6, 9, 10번째 문자를 추출).
[제약 조건]
• $1 \le |S| \le 2000$
• $1 \le |T| \le 2000$
• $S, T$ 는 영소문자로 이루어진 문자열입니다.
입력 설명
첫째 줄에 문자열 $S$ 가 주어집니다.
둘째 줄에 문자열 $T$ 가 주어집니다.
둘째 줄에 문자열 $T$ 가 주어집니다.
출력 설명
최장 공통 부분 수열의 길이를 출력하십시오.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
mynavi
monday
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3