सी प्रोग्राम में एलसीएस का एक अंतरिक्ष अनुकूलित समाधान?

यहां हम एलसीएस समस्या के लिए एक स्थान अनुकूलित दृष्टिकोण देखेंगे। LCS सबसे लंबा सामान्य परिणाम है। यदि दो तार "BHHUBC" और "HYUYBZC" हैं, तो बाद की लंबाई 4 है। एक गतिशील प्रोग्रामिंग दृष्टिकोण पहले से ही उनका है, लेकिन गतिशील प्रोग्रामिंग दृष्टिकोण का उपयोग करके, यह अधिक स्थान लेगा। हमें क्रम की तालिका m x n चाहिए, जहां m पहली स्ट्रिंग में वर्णों की संख्या है, और n दूसरी स्ट्रिंग में वर्णों की संख्या है।

यहां हम देखेंगे कि ओ (एन) सहायक स्थान की मात्रा का उपयोग करके इस एल्गोरिदम को कैसे कार्यान्वित किया जाए। यदि हम पुराने दृष्टिकोण का पालन करते हैं तो हम प्रत्येक पुनरावृत्ति में देख सकते हैं, हमें पिछली पंक्ति से डेटा चाहिए। सभी डेटा की आवश्यकता नहीं है। अतः यदि हम 2n आकार की तालिका बनाते हैं, तो यह ठीक रहेगा। आइए विचार प्राप्त करने के लिए एल्गोरिथम देखें।

एल्गोरिदम

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