सबसे लंबा कॉमन सबसीक्वेंस

सबसे लंबा कॉमन सबसीक्वेंस (LCS) एक प्रकार का सबसीक्वेंस है जो दी गई दोनों सीक्वेंस या ऐरे में मौजूद होता है।

हम देख सकते हैं कि कई सबप्रॉब्लम्स हैं, जिन्हें इस समस्या को हल करने के लिए बार-बार गणना की जाती है। डायनामिक प्रोग्रामिंग के ओवरलैपिंग सबस्ट्रक्चर प्रॉपर्टी का उपयोग करके, हम कम्प्यूटेशनल प्रयासों को कम कर सकते हैं। एक बार सबप्रॉब्लम्स के परिणाम गणना करके टेबल में स्टोर हो जाने पर, हम पिछले परिणामों का उपयोग करके अगले परिणामों की गणना कर सकते हैं।

इनपुट और आउटपुट

इनपुट: अलग-अलग अक्षरों या प्रतीकों वाली दो स्ट्रिंग्स।
स्ट्रिंग 1: AGGTAB
स्ट्रिंग 2: GXTXAYB

आउटपुट: सबसे लंबे कॉमन सबसीक्वेंस की लंबाई। यहां यह 4 है।
AGGTAB और GXTXAYB। अंडरलाइन किए गए अक्षर दोनों स्ट्रिंग्स में हैं और सही क्रम में हैं।

एल्गोरिदम

longestComSubSeq(str1, str2)

इनपुट: LCS की लंबाई ढूंढने के लिए दो स्ट्रिंग्स
आउटपुट: LCS की लंबाई

शुरुआत
    m := str1 की लंबाई
    n := str2 की लंबाई
    (m+1) x (n+1) ऑर्डर की longSubSeq मैट्रिक्स परिभाषित करें
    i := 0 से m तक, करें
        j := 0 से n तक, करें
            यदि i = 0 या j = 0, तो
                longSubSeq[i,j] := 0
            अन्यथा यदि str1[i-1] = str2[j-1], तो
                longSubSeq[i,j] := longSubSeq[i-1,j-1] + 1
            अन्यथा
                longSubSeq[i,j] := longSubSeq[i-1, j] और longSubSeq[i, j-1] का अधिकतम
        पूर्ण
    पूर्ण
    longSubSeq[m, n]
अंत

उदाहरण (C++ कोड)

#include <iostream>
using namespace std;

int max(int a, int b) {
    return (a > b) ? a : b;
}

int longestComSs(string str1, string str2) {
    int m = str1.size();
    int n = str2.size();
    int longSubSeq[m+1][n+1];
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                longSubSeq[i][j] = 0;
            else if (str1[i-1] == str2[j-1])
                longSubSeq[i][j] = longSubSeq[i-1][j-1] + 1;
            else
                longSubSeq[i][j] = max(longSubSeq[i-1][j], longSubSeq[i][j-1]);
        }
    }
    return longSubSeq[m][n];
}

int main() {
    string str1 = "AGGTAB";
    string str2 = "GXTXAYB";
    cout << "Length of Longest Common Subsequence is: " << longestComSs(str1, str2);
}

आउटपुट

Length of Longest Common Subsequence is: 4