LCS(Longest Common Subsequence)

📌 LCS(Longest Common Subsequence)

1. 정의

두 문자열(또는 수열)이 주어졌을 때, 공통으로 나타나는 부분 수열(subsequence) 중 가장 긴 것을 찾는 것이다.

부분 수열은 순서를 유지하지만 연속일 필요는 없다.

X = "ACAYKP"
Y = "CAPCAK"

 

이렇게 두 문자열이 주어졌을 때 가능한 공통 부문 수열은 "ACAK", "CAPK", "CAK" ... 등이 있는데 이중 최장 부분 수열은 "ACAK", "CAPK" 가 되며 길이는 4가된다.

이 알고리즘은 DP로 풀어 갈 수 있다. 현재 문자열위치가 같으면 이전 값을 보고 최대값을 구할 수 있기 때문이다.

2. 점화식(DP 관계식)

문자열 X[1...m], Y[1...n] 에대해서

if X[i] == Y[j] :
    dp[i][j] = dp[i-1][j-1] + 1
else :
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

dp[i][j] = X[1...i]와 Y[1...j]의 LCS 길이가 되며, 최종 답은 dp[m][n]이 된다.

X = "ACAYKP"
Y = "CAPCAK"

 

 

처음에는 0번째 인덱스들을 0으로 채워준다.

 

그리고 순서대로 비교해주면 된다.

같은 문자가 나온다면 이전 값에서 1을 더해주고 값이 다르다면 이전행, 이전열 중 큰 값으로 채워주고 마지막 칸의 값이 LCS의 길이가 된다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String inputA = br.readLine();
        String inputB = br.readLine();

        char[] arrA = new char[inputA.length()+1];
        char[] arrB = new char[inputB.length()+1];
        int[][] dp =  new int[inputA.length()+1][inputB.length()+1];

        for(int i =1;i<=inputA.length();i++){
            arrA[i] = inputA.charAt(i-1);
        }

        for(int i =1;i<=inputB.length();i++){
            arrB[i] = inputB.charAt(i-1);
        }

        for(int i=1;i<=inputA.length();i++){
            for(int j=1;j<=inputB.length();j++){
                if(arrA[i] == arrB[j]){
                    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[inputA.length()][inputB.length()]);
    }
}