LCS (Longest Common Subsequence)

LCS (Longest Common Subsequence = 최장 공통 부분 수열)

acbaed
abcadf

위의 두 문자열이 있을때 순서를 유지하는 부분수열의 같은 최대 길이를
구하는 알고리즘이다.

위 예제 답으로 abad, acad 두 가지 경우가 있다.
우선 공백 문자열에 대해서 1행과 1열을 모두 0으로 초기화한다.
그 후 아래 표와 같이 테이블을 만든다.

str1[l] == str2[u] 일때
    table[l][u] = table[l-1][u-1] + 1
else
    table[l][u] = max(table[l][u-1], table[l-1][u])


table[6][6]에 LCS의 답, 길이가 들어있다.
table[6][6]에서 시작하여 추적하면 LCS문자열도 구할 수 있다.

[-] Collapse

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int table[100][100];
string str1, str2;
void make_lcs(){
        //left string index
    for (int l = 1; l <= str1.size(); l++){
           //upper string index
        for (int u = 1; u <= str2.size(); u++){
            if (str1[l - 1] == str2[u - 1])
                table[l][u] = table[l - 1][u - 1] + 1;
            else
                table[l][u] = max(table[l][u - 1], table[l - 1][u]);
        }
    }
    return;
}
string trace(){
    string str = ""; //역추적 결과를 저장
    int l = str1.size();
    int u = str2.size();
    while (l > 0 && u > 0){
        if (str1[l - 1] == str2[u - 1]) {
            str += str1[l - 1];
            l--, u--;
        }
        else{
            if (table[l][u - 1] >= table[l - 1][u])
                u--;
            else
                l--;
        }

    }
    return str;
}
int main(){
    freopen("input.txt", "r", stdin);
    cin >> str1 >> str2;
    make_lcs();

    cout << "result is length " << table[str1.size()][str2.size()] << endl;

    string result = trace();
    reverse(result.begin(), result.end());

    cout << result << endl << endl;

    for (int i = 0; i <= str1.size(); i++){
        for (int j = 0; j <= str2.size(); j++){
            cout << table[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}