LCS 알고리즘

 

 

 

LCS 알고리즘 

- 최장 공통 부분 수열 또는 최장 공통 문자열을 의미한다.

- 최장 공통 부분 수열 : (ABCDEF, GBCDFE) -> BCDF, BCDE

- 최장 공통 문자열 : (ABCDEF, GBCDFE) -> BCD

 

 

1. 최장 공통 문자열

 

특징

- 연속해서 같아야 한다.

 

 

점화식

- 만약 문자가 같다면 현재 각각의 문자열의 인덱스-1 위치의 값(그 전에 일치했는지 여부)에 + 1 을 해주면 된다.

 

 

시간복잡도

- O(NM)

 

 

예시

- 문자열1 : ABCDEF <-> 문자열2 : GBCDFE

- 두번째 인덱스에서 B가 같은데, 문자열1, 문자열2의 해당 인덱스에서 한칸씩 앞에서도 같은지 확인하고 더해주는 원리이다.

		A	B	C	D	E	F
	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	0	0	0	0
C	0	0	0	2	0	0	0
D	0	0	0	0	3	0	0
F	0	0	0	0	0	0	1
E	0	0	0	0	0	1	0

 

 

코드

int[][] dp = new int[n+1][m+1];
for(int i=0; i<=n; i++){
    for(int j=0; j<=m j++){
        if(i == 0 | j == 0){
            dp[i][j] = 0;
            continue;
        }
        if(value1.charAt(i-1) == value2.charAt(j-1)){
            dp[i][j] = dp[i-1][j-1] + 1;
        }
    }
}

 

 

 

2. 최장 공통 부분 수열

 

특징

- 연속해서 같아야 한다.

 

 

점화식

- 만약, 두 문자가 같다면, dp[i-1][j-1]+1

- 만약, 두 문자가 다르다면, Math.max(dp[i-1][j], dp[i][j-1]);

 

 

시간복잡도

- O(NM)

 

 

예시

- 문자열1 : ABCDEF <-> 문자열2 : GBCDFE

- 예시1 : (3, 3)에서 B 값이 같아서 1이 더해진다. 이 후, (GB <-> ABC) = 1, (GB <-> ABCD) = 1, (GB <-> ABCDE) = 1과 같이 처리

- 예시2 : (4, 3)는 (GBC <-> AB) 관계인데, C와 B는 다르다. 따라서, (GB<->AB), (GB<->A) 중 최대값으로 처리된다.

- 예시3 : (6, 7)은 (GBCDF <-> ABCDEF) 관계인데, GBCD<->ABCDE 관계에서 최대 몇개 같았냐를 파악해야 한다.

		A	B	C	D	E	F
	0	0	0	0	0	0	0
G	0	0	0	0	0	0	0
B	0	0	1	1	1	1	1
C	0	0	1	2	2	2	2
D	0	0	1	2	3	3	3
F	0	0	1	2	3	3	4
E	0	0	1	2	3	4	4

 

 

코드

int[][] dp = new int[n+1][m+1];
for(int i=0; i<=n; i++){
    for(int j=0; j<=m j++){
        if(i == 0 | j == 0){
            dp[i][j] = 0;
            continue;
        }
        if(value1.charAt(i-1) == value2.charAt(j-1)){
            dp[i][j] = dp[i-1][j-1] + 1;
            continue;
        }
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
}

 

 

 

결과 값 찾기

 

1. 마지막 셀(dp[i][j])에서 시작

2. dp[i-1][j], dp[i][j-1] 중 값이 같은 곳으로 이동

3. 값이 같은 곳이 없다면 dp[i-1][j-1]로 이동하고 기존 값 (dp[i][j] 삽입)

4. 반복

 

 

 

전체 구현 코드

package LCS;

import java.util.*;

public class LCSTEST {
    public static int[][] LCS;
    public static String X = "GBCDFE";
    public static String Y = "ABCDEF";
    public static int n;
    public static int m;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println(X);
        System.out.println(Y);
        n = X.length();
        m = Y.length();
        LCS = new int[n+1][m+1];
        for(int i=0; i<n+1; i++){
            for(int j=0; j<m+1; j++){
                if(i == 0 | j == 0){
                    continue;
                }
                if(X.charAt(i-1) == Y.charAt(j-1)){
                    LCS[i][j] = LCS[i-1][j-1] + 1;
                    continue;
                }
                LCS[i][j] = Math.max(LCS[i-1][j], LCS[i][j-1]);
            }
        }
        dfs(new ArrayList<>(), n, m);
    }
    public static void dfs(List<Character> list, int x, int y){
        if(list.size() == LCS[n][m]){
            System.out.println(list);
            return;
        }
        if(x-1 < 0 | y-1 < 0){
            return;
        }
        if(LCS[x][y] == LCS[x-1][y]){
            dfs(list, x-1, y);
        }
        if(LCS[x][y] == LCS[x][y-1]){
            dfs(list, x, y-1);
        }
        if(LCS[x][y] != LCS[x-1][y] && LCS[x][y] != LCS[x][y-1]){
            list.add(X.charAt(x-1));
            dfs(list, x-1, y-1);
            list.remove(list.size()-1);
        }
    }
}

 

 

 

 

관련 문제

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

9251번: LCS

 

 

참고

https://velog.io/@emplam27/알고리즘-그림으로-알아보는-LCS-알고리즘-Longest-Common-Substring와-Longest-Common-Subsequence#longest-common-subsequence-substring

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence