[알고리즘] LCS (Longest Common Subsequence, Longest Common Substring)

 

 

LCS

Longest Common Subsequence는 최장 공통 부분 문자열로, Substring의 값을 구하는 것이 아니라

연속되지 않은 부분 문자열 중 가장 긴 공통 문자열을 찾는 알고리즘이다.

 

반대로, Longest Common Substring은 비슷하지만 부분 문자열이 아닌, substring이 되는 문자열이다.

 

예를들어 ABCDEF, BCDFQQ라는 문자열이 주어지면
Longest Common Subsequence는 BCDF가 되고
Longest Common Substring은 BCD가 된다.

 

 

LCS의 길이를 구할 때는 DP(Dynamic Programming)를 통해 메모제이션으로 효율적인 문제 해결이 가능하다.

 

 

 

점화식

char[] w1 = word1.toCharArray();
char[] w2 = word2.toCharArray();

 

 

위와 같이, 문자열을 배열로 변환했다고 가정하고, 아래와 같이 점화식을 작성할 수 있다.

Substring과 Subsequence의 차이는 공통 문자열이 이어지느냐 이어지지 않느냐의 차이이다.

//Longest Common Substring
if (w1[i - 1] == w2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;
}
else {
    //공통 문자열이 끝났기 때문에 초기화
    dp[i][j] = 0;
}

//Longest Common Subsequence
if (w1[i - 1] == w2[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]);
}

 

 

 

점화식의 이해를 돕기위해 각각의 상황을 위의 예시인 ABCDEF / BCDEFQQ를 가지고 그림으로 그려보았다.

 

 

Longest Common Substring

 

 

 

 

 

 

 

Longest Common Subsquence

부분 문자열에서는, substring과 다르게 계속해서 이전 메모된 값들 중 Max값을 가져가야한다.

(연속된 문자열이 아니기 때문)

 

 

 

 

 

 

 

 

 

예제 - 백준 9251번: LCS

https://www.acmicpc.net/problem/9251

 

 

위에서 설명했던 것 처럼 점화식은 아래와 같다.

if (w1[i - 1] == w2[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]);
}

 

 

단순 최대 길이를 출력하는 것이기 때문에 dp배열의 가장 끝 idx에 최대길이가 저장되게 된다.

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String word1 = br.readLine();
        String word2 = br.readLine();
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];

        char[] w1 = word1.toCharArray();
        char[] w2 = word2.toCharArray();
        for (int i = 1; i <= word1.length(); i ++) {
            for (int j = 1; j <= word2.length(); j ++) {
                if (w1[i - 1] == w2[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[word1.length()][word2.length()]);
    }

}

 

 

 

 

 

 

관련 문제

https://leetcode.com/problems/longest-common-subsequence/description/