LCS

개요

Longest Common Subsequence.

최장 공통 부분수열

문자열 A = “ABCDE” , B = “KBCE” 라고 하자

→ 최장 공통 부분 수열 : BCE

점화식 (LCS의 길이)

1. 문자열 A와 문자열 B를 한글자씩 비교한다.
2. 1. 두 문자가 다르다면, dp[i-1][j]와 dp[i][j-1] 중 큰값을 기록한다.
   2. 두 문자가 같다면, dp[i-1][j-1]의 값에 1을 더한값을 기록한다.
3. 반복

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		String first = in.readLine();
		String second = in.readLine();
		int length1 = first.length();
		int length2 = second.length();

		int[][] dp = new int[length1 + 1][length2 + 1];
		for (int i = 1; i <= length1; ++i) {
			for (int j = 1; j <= length2; ++j) {
				if (first.charAt(i - 1) == second.charAt(j - 1)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		System.out.println(dp[length1][length2]);
	}
}

점화식 ( LCS 문자열 )

1. LCS 배열의 가장 마지막 값에서 시작.
2. dp[i-1][j]와 dp[i][j-1] 중 현재 값과 같은 값을 찾는다.
   1. 같은 값이 있다면, 해당 값으로 이동
   2. 같은 값이 없다면, result에 해당 문자르 추가하고 dp[i-1][j-1]로 이동
3. 반복, dp[i][j]==0으로 이동하면 종료, result 문자의 reverse가 LCS