Giải pháp tối ưu bộ nhớ cho bài toán LCS trong C

Chúng ta sẽ xem cách tiếp cận tối ưu không gian cho bài toán LCS (Longest Common Subsequence - Dãy con chung dài nhất). Nếu hai chuỗi là "BHHUBC" và "HYUYBZC", độ dài dãy con chung là 4. Cách quy hoạch động thường dùng bảng kích thước m x n (m, n là độ dài hai chuỗi), tốn nhiều bộ nhớ.

Ở đây ta cài đặt thuật toán chỉ dùng O(n) không gian phụ. Quan sát cách cũ: mỗi lần lặp chỉ cần dữ liệu từ hàng trước. Không cần toàn bộ bảng. Nếu dùng bảng kích thước 2 x n thì đủ. Xem thuật toán để hiểu rõ.

Thuật toán

lcs_problem(X, Y) -

bắt đầu
    m := độ dài X
    n := độ dài Y
    định nghĩa bảng L[2, n+1]
    index trỏ đến hàng 0 hoặc 1 của bảng L.
    với i từ 1 đến m, làm
        index := index AND 1
        với j từ 0 đến n, làm
            nếu i = 0 hoặc j = 0, thì
                L[index, j] := 0
            khác nếu X[i - 1] = Y[j - 1], thì
                L[index, j] := L[1 – index, j - 1] + 1
            khác
                L[index, j] := max của L[1 – index, j] và L[index, j-1]
            kết thúc nếu
        xong
    xong
    trả về L[index, n]
kết thúc

Ví dụ

#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);
}

Kết quả

Length of LCS is :4