सबसे छोटा सामान्य सुपर अनुक्रम

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

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

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

Input:
Two strings. “ABCDEF” and “XYDEF”
Output:
The length of the shortest common super-sequence.
Here the super-sequence is “ABCDEFXY”. So the length is 8.

एल्गोरिदम

superSeq(str1, str2)

इनपुट: दो तार str1 और str2।

आउटपुट: सुपर सीक्वेंस की लंबाई ज्ञात कीजिए।

Begin
   m := length of str1
   n := length of str2
   define table named seqTab of size (m+1 x n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0, then
            seqTab[i, j] := j
         else if j = 0, then
            seqTab[i, j] := i
         else if str1[i-1] = str2[j-1], then
            seqTab[i, j] := 1 + seqTab[i-1, j-1]
         else
            seqTab[i, j] := 1 + minimum of seqTab[i-1, j] and seqTab[i, j-1]
      done
   done
   return seqTab[m, n]
End

उदाहरण

#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;              //shortest supersequence length is j
         else if (!j)
            supSeqTable[i][j] = i;                //shortest supersequence length is 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