LCS 9

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

문자열의 접두사는, 문자열의 뒤에서 0개 이상의 문자를 제거해서 만들 수 있는 비지 않은 문자열을 뜻한다. 모든 길이 $N$의 문자열은 $N$ 개의 접두사를 가진다.

문자열의 부분문자열은, 문자열의 앞과 뒤에서 0개 이상의 문자를 제거해서 만들 수 있는 비지 않은 문자열을 뜻한다. 모든 길이 $N$의 문자열은 $N(N+1)/2$ 개의 부분문자열을 가진다.

두 문자열이 주어질 때, 첫번째 문자열의 모든 접두사와 두번째 문자열의 모든 부분문자열 쌍에 대해서 LCS의 길이의 합을 구해서 출력하라.

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 7000글자로 이루어져 있다.

첫째 줄에 문제의 정답을 출력하라.