[백준 9251번] LCS :: 늦깎이 IT

[ LCS란? ]

LCS란 Longest Common Subsequence의 약자로 최장 공통 부문 문자열이다. 여기서 Subsequence란 연속적이지 않은 부분 문자열이다.

다음과 같은 문자열 A와 B가 있다고 하자. A = { ABCBDAB } // B = { BCDB }

이때 문자열 B는 문자열 A의 Subsequence이다. 위처럼 연속적이지는 않지만, 순서는 맞는 문자열을 Subsequence라고 한다.

LCS는 두 개의 문자열이 주어졌을 때, Common Subsequence들 중 가장 긴 문자열을 뜻한다.

[ 생각해보기 ]

아래 그림과 같이 문자열 A와 B가 있다고 가정하자.

LCS의 마지막 문자가 A라고 한다면, 문자열 X와 Y 어딘가에도 문자열 A를 포함하고 있을 것이다.

그렇다면, 아래 그림에 표시된 문자열 X''와 Y'', LCS''의 관계에 대해서 생각해보자. LCS의 마지막 문자 A를 제외한 LCS"" 또한 X""와 Y""의 LCS임을 유추할 수 있다.

[ 수식 세우기 ]

문자열 X와 Y의 각각의 문자에 넘버링을 붙이고, 함수 L[ i, j ] 에 대해 다음 그림과 같이 정의한다.

1. 마지막 문자가 같을 때

문자열 X와 Y의 마지막 문자가 같을 때, LCS의 길이는 다음과 같이 나타낼 수 있다.

2. 마지막 문자가 다를 때

문자열 X와 Y의 마지막 문자가 다를 때, LCS의 길이는 다음과 같이 나타낼 수 있다.

즉, 이를 점화식으로 다시 표현하면 다음과 같다.

[ JAVA 코드 ]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
 
    public static void main(String[] args) throws IOException {
 
        String str1 = br.readLine();
        String str2 = br.readLine();
        System.out.println(getLCS(str1, str2));
 
    }
 
    public static int getLCS(String str1, String str2) {
 
        int n = str1.length();
        int m = str2.length();
 
        int[][] lcs = new int[n + 1][m + 1];
 
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
 
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                else
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
            }
        }
        return lcs[n][m];
    }
}