LCS(Longest Common Subsequence - 최장 공통 수열) 알고리즘

Longest Common Subsequence 그리고 Longest Common Substring

LCS에는 최장 공통부분수열(Longest Common Subsequence)과 최장 공통 문자열(Longest Common Substring)을 말한다.

 

문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면

출처:emplam27(사진에 링크 첨부함)

위 그림처럼

 Subsequence은 연속적일 필요 없이 문자를 뛰어넘어도 되지만 Substring 같은 경우에는 문자가 아예 일치해야만 한다.

이를 토대로 각각 점화식을 만들어보면 다음과 같다.

Substring

if (A[i] == B[j])
	dp[i][j] = dp[i - 1][j - 1] + 1;
else
	dp[i][j] = 0;

 Subsequence

if (A[i] == B[j])
	dp[i][j] = dp[i - 1][j - 1] + 1;
else
	dp[b][a] = Math.max(dp[a-1][b],dp[a][b-1]);

해당점화식으로 푼 간단한 dp문제)

9251번: LCS

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

public class V9251 {
    public static char[] A,B;
    public static Integer dp[][]= new Integer[1000][1000];
    public static int lsc(int a,int b){
        if(a<0 || b<0 )
            return 0;
        if(dp[b][a]==null){
            dp[b][a]=0;
            if(A[a]==B[b])
                dp[b][a]=lsc(a-1,b-1)+1;
            else
                dp[b][a]=Math.max(lsc(a-1,b),lsc(a,b-1));

        }
        return dp[b][a];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        A= br.readLine().toCharArray();
        B= br.readLine().toCharArray();
        System.out.println(lsc(A.length-1,B.length-1));




    }
}