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