C प्रोग्राम में LCS का स्पेस ऑप्टिमाइज़्ड समाधान?

यहां हम LCS समस्या के लिए एक स्पेस ऑप्टिमाइज़्ड दृष्टिकोण देखेंगे। LCS सबसे लंबा कॉमन सबसीक्वेंस (Longest Common Subsequence) है। यदि दो स्ट्रिंग्स "BHHUBC" और "HYUYBZC" हैं, तो सबसीक्वेंस की लंबाई 4 है। एक डायनामिक प्रोग्रामिंग दृष्टिकोण पहले से मौजूद है, लेकिन डायनामिक प्रोग्रामिंग दृष्टिकोण का उपयोग करने पर अधिक स्पेस लगेगा। हमें m x n क्रम की टेबल की आवश्यकता होगी, जहां m पहली स्ट्रिंग में वर्णों की संख्या है, और n दूसरी स्ट्रिंग में वर्णों की संख्या है।

यहां हम देखेंगे कि इस एल्गोरिदम को O(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