LCS

들어가기에 앞서

부분 문자열?

①Substring ? 연속된 부분 문자열

②Subsequence ? 연속되지 않은 부분 문자열

예시로 ACDEF와 ABKEF가 있다고 하자.

substring = EF

     ACDEF

     ABKEF

subsequece = AEF

    ACDEF

    ABKEF

---

LCS (Longest Common Subsequence, 최장 공통 부분 문자열)

• 개념 : 두개의 문자열을 비교해 공통 부분 수열을 구하는 알고리즘
• 사용처 : 염기 서열 유사성 분석 or 음파 담어 검색 등
• 구현 방법 : DP(동적분석법)으로 특정 범위까지 memoization하고, 다음 범위를 구할때 이전에 저장한 값을 이용해 품.

---

예시로 ACAYKP, CAPCAK 문자열의 LCS를 구해보자.

참고

* 테이블의 첫번째 열과 첫번째 행은 0으로 채워둔다 (계산의 용이성을 위해)

* 하나의 문자열을 기준 문자열로 잡고, 다른 문자열을 비교 문자열로 둔다.

지금은 ACAYKP를 기준 문자열, CAPCAK 비교 문자열로 사용해 보겠다.

일단 첫번째로 CAPCAK 단어 중 첫번째 단어인 C만 이용해서 ACAYKP와 비교해보겠다.

((테이블 안에 들은 수는 공통 부분 문자열의 개수이다.))

그다음 CAPCAK 중 CA를 비교해보겠다.

이런식으로 테이블을 작성하다 보면 규칙을 발견할 수 있다.

(행은 이전 행의 값을 기반으로 계산된다는 점.)

현재 테이블에 들어갈 수는 

비교문자가 같을 때 -> 이전까지의 LCS 길이 + 1

                              즉, 왼쪽 대각선 값 + 1

비교문자가 다를 때 -> 이전까지의 LCS 길이

                              즉, 왼쪽과 위쪽 중 큰 값

규칙을 통해 만들어진 최종적인 테이블을 아래와 같다.

결과적으로 LCS의 길이를 구할 수 있다. = 4

그렇다면 길이가 아닌 LCS의 해당하는 부분 수열을 구하는 방법은?

가장 오른쪽 아래부터 시작한다.

1. 자신과 같은 숫자가 있는 곳으로 이동한다.

2. 왼쪽과 위쪽에 같은 수가 없다면, 대각선 방향이 현재 값 -1인지 보고 그 수로 이동한다.

   (비교 문자가 같을때 왼쪽 대각선에서 +1 했으니, 이제는 반대로 가는 것이다.)

이를 계속 반복하다 0을 만나면 그만한다.

ACAYKP, CAPCAK 문자열의 LCS는 ACAK 이다.

---

실제  LCS 구현 코드는 아래에 있다

[백준] 9252 LCS2 문제의 정답

#include <stdio.h>
#include <string>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
string f, s;
int dp[1001][1001];
 
int main() {
    cin >> f >> s;
    // 첫번째행과 첫번째열이 0이여야하니깐 계산상 편의를 위해 문자열 앞에 의미없는 걸 붙여둔다.
    f.insert(f.begin(), '0'); 
    s.insert(s.begin(), '0');
    //1. 테이블 채우기
    for (int i = 1; i < f.length(); i++) {
        for (int j = 1; j < s.length(); j++) {
            if (f[i] == s[j]) { // 문자가 같다면, 왼쪽 대각선 값 + 1
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {//문자가 다르면, 왼쪽과 위쪽 값 중 큰 값
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
    }
    printf("%d\n", dp[f.length()-1][s.length()-1]);
    vector <char> temp;
    //2. 문자열 구하기
    int i = f.length() - 1;
    int j = s.length() - 1;
    while (dp[i][j] != 0) {
        //같은 숫자있다면 이동
        if (dp[i][j] == dp[i][j - 1]) {
            j -= 1;
        }
        else if (dp[i][j] == dp[i - 1][j]) {
            i -= 1;
        }
        else if (dp[i][j] == dp[i - 1][j - 1] + 1) {
            temp.insert(temp.begin(),f[i]); //거꾸로 삽입되지 않기 위해, 처음에 계속 삽입
            i -= 1;
            j -= 1;
 
        }
    }
    for (int i = 0; i < temp.size(); i++) {
        printf("%c", temp[i]);
    }
 
    return 0;
}