Một giải pháp tối ưu hóa không gian của LCS trong Chương trình C?

Ở đây chúng ta sẽ thấy một cách tiếp cận được tối ưu hóa không gian cho vấn đề LCS. LCS là dãy con chung dài nhất. Nếu hai chuỗi là “BHHUBC” và “HYUYBZC”, thì độ dài của dãy con là 4. Một phương pháp lập trình động đã là của chúng, nhưng sử dụng phương pháp lập trình động, sẽ tốn nhiều dung lượng hơn. Chúng ta cần bảng thứ tự m x n, trong đó m là số ký tự trong chuỗi đầu tiên và n là số ký tự trong chuỗi thứ hai.

Ở đây chúng ta sẽ xem cách thực hiện thuật toán này bằng cách sử dụng O (n) lượng không gian bổ trợ. Nếu chúng ta quan sát cách tiếp cận cũ, chúng ta có thể thấy trong mỗi lần lặp, chúng ta cần dữ liệu từ hàng trước đó. Không phải tất cả dữ liệu đều được yêu cầu. Vì vậy, nếu chúng ta làm một bảng có kích thước 2n, thì nó sẽ không sao cả. Hãy để chúng tôi xem thuật toán để có được ý tưởng.

Thuật toá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

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

Đầu ra

Length of LCS is :4