सी ++ प्रोग्राम सबसे छोटा सुपरसीक्वेंस खोजने के लिए जिसमें बाद के रूप में दो या दो से अधिक सीक्वेंस होते हैं

यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे, जिसमें सबसे छोटी सुपरसीक्वेंस की खोज की जाएगी, जिसमें बाद के रूप में दो या दो से अधिक सीक्वेंस हों।

एल्गोरिदम

Begin
   function ShortestSubSeq() returns supersequence of A and B:
   1) Declare an array ss[i][j] which contains length of shortest supersequence for A[0 .. i-1] and B[0 .. j-1].
   2) Find the length of the possible supersequence in bottom up manner using recursion.
   3) Declare an array ss[i][j] which stores length of shortest supersequence for A[0 .. i-1] and B[0 .. j-1] in index.
   4) Declare a string s to store the shortest subsequence.
   5) Initialize i = a, j = b.
   6) while (i > 0 and j > 0)
      A) If current character in A and B are same, then current character is part of shortest supersequence.
      Put current character in result.
      Reduce values of i, j and index.
      B) Else if
      If current character in A and B are different,
      Put current character of B in result.
      Reduce values of j and index.
      C) Else
      Put current character of A in result.
      Reduce values of i and index.
   7) While (i > 0)
   Put remaining characters of A in the result string.
   8) While(j>0)
   Put remaining characters of B in the result string.
   9) Reverse the string and return it.
End

उदाहरण

#include <bits/stdc++.h>
using namespace std;
string ShortestSuperSeq(string A, string B) {
   int a = A.length();  
   int b = B.length();
   int ss[a + 1][b + 1];
   for (int i = 0; i <= a; i++) {
      for (int j = 0; j <= b; j++) {
         if(i == 0)
            ss[i][j] = j;
         else if(j == 0)
            ss[i][j] = i;
         else if(A[i - 1] == B[j - 1])
            ss[i][j] = 1 + ss[i - 1][j - 1];
         else
            ss[i][j] = 1 + min(ss[i - 1][j], ss[i][j - 1]);
      }
   }
   int index = ss[a][b];
   string s;
   int i = a, j = b;
   while (i > 0 && j > 0) {
      //If current character in A and B are same, then current character is part of shortest supersequence
      if (A[i - 1] == B[j - 1]) {
         //Put current character in result.
         //reduce values of i, j and index.
         s.push_back(A[i - 1]);
         i--, j--, index--;
      }
      //If current character in A and B are different,
      else if (ss[i - 1][j] > ss[i][j - 1]) {
         //Put current character of B in result.
         //reduce values of j and index.
         s.push_back(B[j - 1]);
         j--, index--;
      }
      //Put current character of A in result.
      //reduce values of i and index.
      else {
         s.push_back(A[i - 1]);
         i--, index--;
      }
   }
   //put remaining characters of A in the result string.
   while (i > 0) {
      s.push_back(A[i - 1]);
      i--, index--;
   }
   //put remaining characters of B in the result string.
   while (j > 0) {
      s.push_back(B[j - 1]);
      j--, index--;
   }
   reverse(s.begin(), s.end()); //Reverse the string and return it.
   return s;
}
int main() {
   string M = "ABBCDDEEFF";
   string N = "ABCDEEEFF";
   cout <<"The Shortest SuperSequence is:"<< ShortestSuperSeq(M, N);
   return 0;
}

आउटपुट

The Shortest SuperSequence is:ABBCDEDEEFF