এখানে আমরা দুটি বা অধিক সিকোয়েন্সকে সাবসিকোয়েন্স হিসেবে ধারণকারী শর্টেস্ট সুপারসিকোয়েন্স (Shortest Supersequence) খুঁজে বের করার C++ প্রোগ্রাম দেখব।
এলগরিদম
Begin
function ShortestSuperSeq() returns supersequence of A and B:
1) ss[i][j] অ্যারে ডিক্লেয়ার করুন যা A[0..i-1] এবং B[0..j-1]-এর শর্টেস্ট সুপারসিকোয়েন্সের দৈর্ঘ্য ধারণ করবে।
2) বটম-আপ (bottom-up) পদ্ধতিতে রিকার্শন ব্যবহার করে সম্ভাব্য সুপারসিকোয়েন্সের দৈর্ঘ্য বের করুন।
3) ss[i][j] অ্যারে ইনডেক্সে দৈর্ঘ্য স্টোর করুন।
4) স্ট্রিং s ডিক্লেয়ার করুন শর্টেস্ট সাবসিকোয়েন্স স্টোর করতে।
5) i = a, j = b ইনিশিয়ালাইজ করুন।
6) while (i > 0 and j > 0)
A) যদি A এবং B-র করেন্ট ক্যারেক্টার সমান হয়, তবে সেটি শর্টেস্ট সুপারসিকোয়েন্সের অংশ। রেজাল্টে যোগ করুন। i, j, index ডিক্রিমেন্ট করুন।
B) Else if: যদি ক্যারেক্টারগুলো ভিন্ন হয়, B-এর ক্যারেক্টার রেজাল্টে যোগ করুন। j, index ডিক্রিমেন্ট করুন।
C) Else: A-এর ক্যারেক্টার রেজাল্টে যোগ করুন। i, index ডিক্রিমেন্ট করুন।
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) {
if (A[i - 1] == B[j - 1]) {
s.push_back(A[i - 1]);
i--, j--, index--;
}
else if (ss[i - 1][j] > ss[i][j - 1]) {
s.push_back(B[j - 1]);
j--, index--;
}
else {
s.push_back(A[i - 1]);
i--, index--;
}
}
while (i > 0) {
s.push_back(A[i - 1]);
i--, index--;
}
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
