यहां हम एक C++ प्रोग्राम पर चर्चा करेंगे जो दो या अधिक सीक्वेंस को सबसीक्वेंस के रूप में समाहित करने वाला सबसे छोटा सुपरसीक्वेंस खोजता है।
एल्गोरिदम
Begin
function ShortestSuperSeq() A और B का सुपरसीक्वेंस लौटाता है:
1) एक ऐरे ss[i][j] घोषित करें जिसमें A[0..i-1] और B[0..j-1] के लिए सबसे छोटे सुपरसीक्वेंस की लंबाई हो।
2) रिकर्सन का उपयोग करके बॉटम-अप तरीके से संभावित सुपरसीक्वेंस की लंबाई खोजें।
3) एक ऐरे ss[i][j] घोषित करें जो इंडेक्स में A[0..i-1] और B[0..j-1] के लिए सबसे छोटे सुपरसीक्वेंस की लंबाई स्टोर करता है।
4) सबसे छोटे सबसीक्वेंस को स्टोर करने के लिए एक स्ट्रिंग s घोषित करें।
5) i = a, j = b इनिशियलाइज़ करें।
6) while (i > 0 और j > 0)
A) यदि A और B में वर्तमान कैरेक्टर समान हैं, तो वर्तमान कैरेक्टर सबसे छोटे सुपरसीक्वेंस का हिस्सा है।
वर्तमान कैरेक्टर को परिणाम में डालें।
i, j और इंडेक्स के मान कम करें।
B) अन्यथा यदि
यदि A और B में वर्तमान कैरेक्टर अलग हैं,
B के वर्तमान कैरेक्टर को परिणाम में डालें।
j और इंडेक्स के मान कम करें।
C) अन्यथा
A के वर्तमान कैरेक्टर को परिणाम में डालें।
i और इंडेक्स के मान कम करें।
7) While (i > 0)
A के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें।
8) While(j > 0)
B के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें।
9) स्ट्रिंग को रिवर्स करें और लौटाएं।
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) {
// यदि A और B में वर्तमान कैरेक्टर समान हैं, तो वर्तमान कैरेक्टर सबसे छोटे सुपरसीक्वेंस का हिस्सा है
if (A[i - 1] == B[j - 1]) {
// वर्तमान कैरेक्टर को परिणाम में डालें
// i, j और इंडेक्स के मान कम करें
s.push_back(A[i - 1]);
i--, j--, index--;
}
// यदि A और B में वर्तमान कैरेक्टर अलग हैं
else if (ss[i - 1][j] > ss[i][j - 1]) {
// B के वर्तमान कैरेक्टर को परिणाम में डालें
// j और इंडेक्स के मान कम करें
s.push_back(B[j - 1]);
j--, index--;
}
// A के वर्तमान कैरेक्टर को परिणाम में डालें
// i और इंडेक्स के मान कम करें
else {
s.push_back(A[i - 1]);
i--, index--;
}
}
// A के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें
while (i > 0) {
s.push_back(A[i - 1]);
i--, index--;
}
// B के शेष कैरेक्टर्स को परिणाम स्ट्रिंग में डालें
while (j > 0) {
s.push_back(B[j - 1]);
j--, index--;
}
reverse(s.begin(), s.end()); // स्ट्रिंग को रिवर्स करें और लौटाएं
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
शॉर्टेस्ट कॉमन सुपरसीक्वेंस (SCS) समस्या LCS (लॉन्गेस्ट कॉमन सबसीक्वेंस) से संबंधित है। SCS की लंबाई = len(A) + len(B) - len(LCS)। यह डायनामिक प्रोग्रामिंग दृष्टिकोण O(m*n) समय और स्थान में SCS का निर्माण करता है।