शॉर्टेस्ट कॉमन सुपर सीक्वेंस

परिचय

शॉर्टेस्ट कॉमन सुपर सीक्वेंस (SCS) एक ऐसा अनुक्रम है जिसमें दोनों दी गई अनुक्रमों के सभी तत्व मौजूद होते हैं। दूसरे शब्दों में, दी गई दोनों स्ट्रिंग्स SCS की सबसीक्वेंस होती हैं।

मूल अवधारणा

जब दो स्ट्रिंग्स में कोई सामान्य वर्ण नहीं होता, तो हम उन्हें केवल जोड़कर सुपरसीक्वेंस प्राप्त कर सकते हैं। लेकिन जब उनमें कुछ सामान्य वर्ण होते हैं, तो पहले हमें सबसे लंबी सामान्य सबसीक्वेंस (LCS) ढूंढनी होती है, फिर दूसरी स्ट्रिंग के अतिरिक्त वर्णों को जोड़ना होता है।

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

इनपुट: दो स्ट्रिंग्स "ABCDEF" और "XYDEF"
आउटपुट: शॉर्टेस्ट कॉमन सुपरसीक्वेंस की लंबाई। यहाँ सुपरसीक्वेंस है "ABCDEFXY"। इसलिए लंबाई 8 है।

एल्गोरिदम

superSeq(str1, str2)
इनपुट: दो स्ट्रिंग्स str1 और str2
आउटपुट: सुपर सीक्वेंस की लंबाई

Begin
    m := str1 की लंबाई
    n := str2 की लंबाई
    (m+1 x n+1) आकार की seqTab नामक टेबल परिभाषित करें
    i := 0 से m तक, करें
        j := 0 से n तक, करें
            यदि i = 0, तो
                seqTab[i, j] := j
            अन्यथा यदि j = 0, तो
                seqTab[i, j] := i
            अन्यथा यदि str1[i-1] = str2[j-1], तो
                seqTab[i, j] := 1 + seqTab[i-1, j-1]
            अन्यथा
                seqTab[i, j] := 1 + min(seqTab[i-1, j], seqTab[i, j-1])
        done
    done
    seqTab[m, n] लौटाएं
End

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

#include <iostream>
using namespace std;

int min(int a, int b) {
    return (a < b) ? a : b;
}

int superSeq(string str1, string str2) {
    int m = str1.size();
    int n = str2.size();
    int supSeqTable[m+1][n+1];
    
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (!i)
                supSeqTable[i][j] = j;
            else if (!j)
                supSeqTable[i][j] = i;
            else if (str1[i-1] == str2[j-1])
                supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];
            else
                supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);
        }
    }
    return supSeqTable[m][n];
}

int main() {
    string first = "ABCDEF";
    string second = "XYDEF";
    cout << "Length of the shortest supersequence is " << superSeq(first, second);
}

आउटपुट

Length of the shortest supersequence is 8