Longest Common Subsequence (LCS)

Longest Common Subsequence (LCS) adalah masalah DP 2D paling fundamental pada string: diberikan dua string s dan t, cari subsequence terpanjang yang muncul pada keduanya. Subsequence tidak harus berurutan (contiguous) tetapi harus menjaga urutan relatif. Masalah ini menjadi dasar untuk diff tools (git), perbandingan DNA, dan analisis kemiripan teks. Pada Chapter ini kita akan membedah state, transisi, optimasi ruang, dan rekonstruksi LCS.

Aturan: Match atau Skip #

Pada LCS, untuk setiap pasangan karakter s[i-1] dan t[j-1]:

• Bila cocok: kedua karakter adalah bagian LCS, tambahkan panjang 1.
• Bila tidak cocok: lewatkan salah satu — ambil maksimum dari dp[i-1][j] (skip s[i-1]) atau dp[i][j-1] (skip t[j-1]).

Mekanisme: DP 2D dengan Recurrence Match/Mismatch #

State: dp[i][j] — panjang LCS dari s[0..i-1] dan t[0..j-1].

Recurrence:

dp[i][j] = dp[i-1][j-1] + 1                  jika s[i-1] == t[j-1]
dp[i][j] = max(dp[i-1][j], dp[i][j-1])       jika tidak

Base case: dp[0][j] = 0 dan dp[i][0] = 0 (salah satu string kosong → LCS 0).

Urutan iterasi: i dari 1 hingga n luar, j dari 1 hingga m dalam. Setiap sel hanya bergantung pada baris sebelumnya atau sel di kiri pada baris yang sama — keduanya sudah dihitung.

Kode: LCS dengan Tabel 2D #

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int lcs(const std::string& s, const std::string& t) {
    int n = static_cast<int>(s.size());
    int m = static_cast<int>(t.size());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

int main() {
    std::string s = "ABCBDAB";
    std::string t = "BDCAB";
    std::cout << "LCS length = " << lcs(s, t) << '\n';
    return 0;
}

Output yang Dihasilkan:

LCS length = 4

1. Baris std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));: tabel (n+1) × (m+1). Baris/kolom 0 diisi 0 sebagai base case.
2. Baris if (s[i - 1] == t[j - 1]): cek apakah karakter ke-i-1 dari s cocok dengan karakter ke-j-1 dari t.
3. Baris dp[i][j] = dp[i - 1][j - 1] + 1;: transisi match. Kedua karakter dimasukkan ke LCS.
4. Baris dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);: transisi mismatch. Lewati satu karakter dari s atau dari t, ambil yang lebih panjang.
5. Hasil 4: LCS adalah "BCAB" atau "BDAB" — panjang 4.

Visualisasi Tabel #

Untuk s = "ABC", t = "AC", tabel DP terlihat seperti:

      ""  A  C
  ""   0  0  0
   A   0  1  1
   B   0  1  1
   C   0  1  2

• Sel [1][1] = 1 karena s[0] = 'A' cocok t[0] = 'A'.
• Sel [3][2] = 2 karena s[2] = 'C' cocok t[1] = 'C', ditambah dp[2][1] = 1.

Rekonstruksi LCS #

Untuk mendapatkan string LCS itu sendiri, kita traceback dari dp[n][m]:

#include <iostream>
#include <vector>
#include <string>

std::string lcs_str(const std::string& s, const std::string& t) {
    int n = static_cast<int>(s.size());
    int m = static_cast<int>(t.size());
    std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // Traceback untuk membangun LCS
    std::string result;
    int i = n, j = m;
    while (i > 0 && j > 0) {
        if (s[i - 1] == t[j - 1]) {
            result.push_back(s[i - 1]);
            --i; --j;
        } else if (dp[i - 1][j] >= dp[i][j - 1]) {
            --i;
        } else {
            --j;
        }
    }
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::string s = "ABCBDAB";
    std::string t = "BDCAB";
    std::cout << "LCS string = " << lcs_str(s, t) << '\n';
    return 0;
}

Output yang Dihasilkan:

LCS string = BCAB

1. Baris while (i > 0 && j > 0): loop mundur dari dp[n][m] ke dp[0][0].
2. Baris if (s[i - 1] == t[j - 1]): bila karakter cocok, ini adalah karakter LCS. Tambahkan ke hasil dan mundur diagonal.
3. Baris else if (dp[i - 1][j] >= dp[i][j - 1]): bila tidak cocok, mundur ke arah nilai yang lebih besar (ke atas bila atas lebih besar atau sama).
4. Baris std::reverse(...): karena kita membangun LCS dari akhir ke awal, perlu dibalik.

Optimasi Ruang: 1D dengan Rolling Array #

Karena dp[i][j] hanya bergantung pada dp[i-1][*] dan dp[i][j-1], kita bisa pakai dua array 1D:

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

int lcs_1d(const std::string& s, const std::string& t) {
    int n = static_cast<int>(s.size());
    int m = static_cast<int>(t.size());
    std::vector<int> prev(m + 1, 0), cur(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (s[i - 1] == t[j - 1]) {
                cur[j] = prev[j - 1] + 1;
            } else {
                cur[j] = std::max(prev[j], cur[j - 1]);
            }
        }
        std::swap(prev, cur);
    }
    return prev[m];
}

int main() {
    std::string s = "ABCBDAB";
    std::string t = "BDCAB";
    std::cout << "LCS (1D) = " << lcs_1d(s, t) << '\n';
    return 0;
}

Output yang Dihasilkan:

LCS (1D) = 4

1. Dua array prev dan cur: prev menyimpan baris i-1, cur menyimpan baris i yang sedang dihitung.
2. Baris cur[j] = prev[j - 1] + 1;: akses prev[j-1] = dp[i-1][j-1].
3. Baris std::swap(prev, cur);: setelah selesai satu baris, tukar peran. Baris berikutnya akan menggunakan cur yang baru sebagai prev.
4. Hasil identik 4: optimasi ruang tidak mengubah jawaban. Memori: O(min(n, m)) alih-alih O(n·m).

Variasi dan Aplikasi #

• Longest Common Substring: harus contiguous. Modifikasi: bila mismatch, set dp[i][j] = 0 (bukan max).
• Shortest Common Supersequence: panjang minimum string yang mengandung s dan t sebagai subsequence. SCS = n + m - LCS.
• Edit distance: mirip LCS tetapi memperbolehkan insert, delete, replace.
• Diff tools: algoritma diff menggunakan LCS untuk menemukan baris yang sama antara dua file.

Tabel Kompleksitas #

Ringkasan #

• LCS: state dp[i][j], transisi match (+1) atau mismatch (max).
• Recurrence: dp[i][j] = dp[i-1][j-1]+1 jika match, max(dp[i-1][j], dp[i][j-1]) jika tidak.
• Rekonstruksi: traceback dari dp[n][m], ikuti karakter yang match.
• Optimasi ruang: dua array 1D (rolling array) untuk O(min(n,m)) memori.
• Aplikasi: diff tools, perbandingan DNA, SCS, dan edit distance.