최장공통문자열(Longest Common Substring - LCS)

  들어가기에 앞서 LCS를 구별하도록 하자. 일반적으로 LCS라고 하면 최장공통부분수열(Longest Common Subsequence)을 뜻하지만, 최장공통 문자열(Longest Common Sustring)도 LCS라고 부르기도 한다. 둘의 차이점은 구하고자 하는 부분 문자열의 연속성이라고 할 수 있다.

  이번 글에서는 최장공통 문자열(Longest Common Substring)에 대해서 먼저 알아보자

 

1. 개념 🦆

  최장공통부분문자열(LCS)은 연속된 부분 문자열 중 가장 길이가 긴 문자열을 말한다. 

 

2. 동작 방식 🐓

  동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자.

1. 문자열 A와 문자열 B를 한 글자씩 비교한다.
2. 비교하는 문자가 같다면 DP[i][j]는 DP[i-1][j-1] + 1이 된다.
   비교하는 문자가 다르다면 DP[i][j]에 0을 표시한다.
3. 1번과 2번 과정을 반복한다.

  예상할 수 있듯이 위에서 말한 DP[i][j]는 문자열 A는 i번째까지 문자열 B는 j번째까지 고려하였을 경우에 얻은 최장공통부분문자열의 길이이다. i와 j는 1부터 문자열의 길이까지 순회를 하고 i 또는 j가 0인 장소의 DP값은 0으로 설정한다.

• 비교하는 문자가 같을 때 'DP[i][j] = DP[i-1][j-1] + 1'을 하는 이유
  이전 상황까지의 최장공통부분문자열에 현재 비교된 같은 문자를 추가하는 과정이다.
• 비교하는 문자가 다를 때 'DP[i][j] = 0'이 되는 이유
  최장공통부분문자열은 연속된 부분 문자열을 전제로 하고 있기 때문에 연속성이 없어지면 0으로 초기화해야 한다.

  'ABCDEF'와 'GBCDFE'를 이용하여 LCS를 구하는 방법을 그림을 이용하여 이해해 보자.

 

3. 구현(JAVA) 🦢

  i 또는 j가 0이라면 DP(비교를 하지 않은 상황)의 값이 0이라는 것만 주의해서 코드를 보도록 하자.

public static void main(String[] args) {
    String A = "ABCDEF";
    String B = "GBCDFE";
    int aStrLen = A.length();
    int bStrLen = B.length();
    // LCS의 길이
    int maxLen = 0;
    int[][] DP = new int[aStrLen + 1][bStrLen + 1];

    for(int i = 1; i <= aStrLen; i++) {
        for(int j = 1; j <= bStrLen; j++) {
            // 비교하는 문자가 같은 경우
            if(A.charAt(i - 1) == B.charAt(j - 1)) {
                DP[i][j] = DP[i - 1][j - 1] + 1;
                maxLen = Math.max(maxLen, DP[i][j]);
            }
            // 비교하는 문자가 다른 경우
            else {
                DP[i][j] = 0;
            }
        }
    }

    System.out.println(maxLen);
}

 

해당 글은 emplam27 님의 '그림으로 알아보는 LCS 알고리즘'을 참고하였습니다.