시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 257 | 149 | 43 | 62.319% |
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
문자열의 접두사는, 문자열의 뒤에서 0개 이상의 문자를 제거해서 만들 수 있는 비지 않은 문자열을 뜻한다. 모든 길이 $N$의 문자열은 $N$ 개의 접두사를 가진다.
문자열의 부분문자열은, 문자열의 앞과 뒤에서 0개 이상의 문자를 제거해서 만들 수 있는 비지 않은 문자열을 뜻한다. 모든 길이 $N$의 문자열은 $N(N+1)/2$ 개의 부분문자열을 가진다.
두 문자열이 주어질 때, 첫번째 문자열의 모든 접두사와 두번째 문자열의 모든 부분문자열 쌍에 대해서 LCS의 길이의 합을 구해서 출력하라.
첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 7000글자로 이루어져 있다.
첫째 줄에 문제의 정답을 출력하라.
ACAYKP CAPCAK
197
WEDONTNEEDNOEDUCATION WEDONTNEEDNOTHOUGHTCONTROL
29813