วิธีแก้ปัญหา LCS แบบประหยัดพื้นที่หน่วยความจำ (Space Optimized) ใน C

ที่นี่เราจะดูวิธีแก้ปัญหา LCS (Longest Common Subsequence) แบบประหยัดพื้นที่หน่วยความจำ ถ้ามีสตริง 2 ตัวคือ "BHHUBC" และ "HYUYBZC" ความยาวของ subsequence ร่วมที่ยาวที่สุดคือ 4 วิธี Dynamic Programming ปกติจะใช้ตารางขนาด m x n ซึ่ง m, n คือความยาวสตริง ใช้พื้นที่มาก

เราจะทำให้ใช้พื้นที่ช่วยเพียง O(n) โดยสังเกตว่าแต่ละรอบต้องการข้อมูลจากแถวก่อนหน้าเท่านั้น ไม่ใช่ทั้งตาราง ดังนั้นใช้ตารางขนาด 2 x n แทนได้ ให้ดูอัลกอริทึมเพื่อเข้าใจแนวคิด

อัลกอริทึม

lcs_problem(X, Y) -

begin
    m := length of X
    n := length of Y
    define table of size L[2, n+1]
    index is to point 0th or 1st row of the table L.
    for i in range 1 to m, do
        index := index AND 1
        for j in range 0 to n, do
            if i = 0 or j = 0, then
                L[index, j] := 0
            else if X[i - 1] = Y[j - 1], then
                L[index, j] := L[1 – index, j - 1] + 1
            else
                L[index, j] := max of L[1 – index, j] and L[index, j-1]
            end if
        done
    done
    return L[index, n]
end

ตัวอย่าง

#include <iostream>
using namespace std;
int lcsOptimized(string &X, string &Y) {
    int m = X.length(), n = Y.length();
    int L[2][n + 1];
    bool index;
    for (int i = 0; i <= m; i++) {
        index = i & 1;
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[index][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[index][j] = L[1 - index][j - 1] + 1;
            else
                L[index][j] = max(L[1 - index][j], L[index][j - 1]);
        }
    }
    return L[index][n];
}
int main() {
    string X = "BHHUBC";
    string Y = "HYUYBZC";
    cout << "Length of LCS is :" << lcsOptimized(X, Y);
}

ผลลัพธ์

Length of LCS is :4