Space-optimized solution for LCS in C program?

Here we will see a spatial optimization method for the LCS problem. LCS is the longest common subsequence. If the two strings are "BHHUBC" and "HYUYBZC", then the length of the subsequence is 4. Dynamic programming method is already one of them, but using dynamic programming method will take up more space. We need a table of order m x n, where m is the number of characters in the first string and n is the number of characters in the second string.

Here we will learn how to use O(n) auxiliary space. If we look at the old approach, we can see that in each iteration, we need the data from the previous row. Not all data is required. So if we make a table of size 2n, that's no problem. Let's look at the algorithm to understand this idea.

Algorithm

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

Example

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

Output

Length of LCS is :4

The above is the detailed content of Space-optimized solution for LCS in C program?. For more information, please follow other related articles on the PHP Chinese website!