ในที่นี้เราจะพูดถึงโปรแกรม C++ เพื่อค้นหา Supersequence ที่สั้นที่สุดที่มีลำดับสองลำดับขึ้นไปเป็นลำดับรอง
อัลกอริทึม
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
