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

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

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

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String fs = sc.nextLine();
        String ss = sc.nextLine();
        int[] dp;
        if (fs.length() >= ss.length()) {
            dp = new int[fs.length()];
        } else {
            dp = new int[ss.length()];
        }

        for (int i = 0; i < fs.length(); i++) {
            int max = 0;
            for (int j = 0; j < ss.length(); j++) {
                if (max < dp[j]) {
                    max = dp[j];
                } else if (fs.charAt(i) == ss.charAt(j)) {
                    dp[j] = max + 1;
                }
            }
        }
        Arrays.sort(dp);
        int answer;
        if (dp.length > 0) {
            answer = dp[dp.length - 1];
        } else {
            answer = dp[0];
        }
        System.out.println(answer);
    }
}

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String x = sc.nextLine();
		String y = sc.nextLine();
		int[][] dp = new int[1001][1001];

		for (int i = 1; i <= x.length(); i++) {
			for (int j = 1; j <= y.length(); j++) {
				if (x.charAt(i - 1) == y.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				}
				else {
					dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
				}
			}
		}

		System.out.println(dp[x.length()][y.length()]);
	}

}

x = input()
y = input()

dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]
for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):
        if x[i - 1] == y[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

print(dp[len(x)][len(y)])