C ++程序查找包含两个或多个序列作为子序列的最短超序列
在这里，我们将讨论一个C++程序，以找到包含两个或多个序列作为子序列的最短超序列。
算法
Begin
函数ShortestSubSeq()返回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) Initialize i = a, j = b.
6) while (i > 0 and j > 0)
A) 如果A和B中的当前字符相同，则当前字符是最短超序列的一部分.
将当前字符放入结果中。
降低i，j和index的值。
B) Else if
如果A和B中的当前字符不同，
在结果中放入B的当前字符。
减少j和index的值。
C) Else
将当前字符A放入结果中。
降低i和index的值。
7) While (i > 0)
将A的其余字符放在结果字符串中。
8) While(j>0)
将B的其余字符放在结果字符串中。
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) {
//如果A和B中的当前字符相同，则当前字符是最短超序列的一部分
if (A[i - 1] == B[j - 1]) {
//将当前字符放入结果中。
//降低i，j和index的值。
s.push_back(A[i - 1]);
i--, j--, index--;
}
//如果A和B中的当前字符不同，
else if (ss[i - 1][j] > ss[i][j - 1]) {
//在结果中放入B的当前字符。
//减少j和index的值。
s.push_back(B[j - 1]);
j--, index--;
}
//将当前字符A放入结果中。
//降低i和index的值。
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 <<"最短的超序列是："<< ShortestSuperSeq(M, N);
return 0;
}输出结果
最短的超序列是：ABBCDEDEEFF