LCS (Longest Common Subsequence)

[WonYong-Jang]

최장 공통 부분 수열 (LCS)

• substring 은 연속된 부분 문자열
• subsequence 은 연속적이지 않은 부분 문자열!! 구분할 것!

LCS 구하기

DP를 이용하여 특정 범위까지의 값을 구하고 다른 범위까지의 값을 구할때 이전에 구해 둔 값을 이용하여 해결

주의 : LCS는 substring을 구하는 것과 다르게 연속적이지 않아도 되기 때문에 같은 길이의 다른해가 나타날 수 있다!

LCS 출력

소스코드

for(int i=1; i<= N; i++) // base case
{
    sn[i] = s.charAt(i-1);
    L[i][0] = 0;
}
for(int i=1; i<= M; i++) // base case 
{
    tm[i] = t.charAt(i-1);
    L[0][i] = 0;
}
for(int i=1; i<= N; i++)
{
    for(int j=1; j<= M; j++)
    {
        if(sn[i] == tm[j]) // 같다면 
        {
            L[i][j] = L[i-1][j-1] + 1;
        }
        else // 다르다면 둘중 큰값으로 
        {
            L[i][j] = max(L[i-1][j], L[i][j-1]);
        }
    }
}
System.out.println(L[N][M]);

전체 소스코드 ( lcs 문자열 출력 함수 포함)

public class baek9252 {

    static int N, M;
    static char[] sn = new char[4005];
    static char[] tm = new char[4005];
    static String s, t, result;
    static int[][] L = new int[4005][4005]; // LCS 길이 
    static int[][] S = new int[4005][4005]; // LCS 문자 추적하기 위한 배열  
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        s = t = "";
        s = br.readLine();
        t = br.readLine();
        result = "";

        N = s.length();
        M = t.length();

        for(int i=1; i<= N; i++) // base case
        {
            sn[i] = s.charAt(i-1);
            L[i][0] = 0;
        }
        for(int i=1; i<= M; i++) // base case 
        {
            tm[i] = t.charAt(i-1);
            L[0][i] = 0;
        }
        for(int i=1; i<= N; i++)
        {
            for(int j=1; j<= M; j++)
            {
                if(sn[i] == tm[j]) 
                {
                    L[i][j] = L[i-1][j-1] + 1;
                    S[i][j] = 0;
                }
                else
                {
                    L[i][j] = max(L[i-1][j], L[i][j-1]);
                    if(L[i][j] == L[i][j-1]) { // 왼쪽에서 왔다면 1로 체킹 
                        S[i][j] = 1;
                    }
                    else { // 오른쪽에서 왔다면 2로 체킹 
                        S[i][j] = 2;
                    }
                }
            }
        }
        solve(N, M);
        System.out.println(L[N][M]);
        System.out.println(result);

    }
    public static void solve(int dx, int dy)
    {
        if(!isRange(dx, dy)) return;

        if(S[dx][dy] == 0)
        {
            solve(dx-1,dy-1);
            result += sn[dx];
        }
        else if(S[dx][dy] == 1) solve(dx,dy-1);
        else if(S[dx][dy] == 2) solve(dx-1, dy);
    }

참고 링크 : http://twinw.tistory.com/126