Siêu trình tự chung ngắn nhất

Siêu dãy phổ biến ngắn nhất là dãy mà mỗi phần tử của cả hai dãy đã cho đều có mặt. Nói cách khác, chúng ta có thể nói rằng hai chuỗi đã cho, cả hai đều là chuỗi con của Siêu chuỗi chung ngắn nhất.

Khi không có ký tự chung nào trong hai chuỗi, thì chúng ta có thể nối chúng một cách đơn giản để có được Siêu chuỗi. Nhưng khi chúng có một số ký tự chung, thì trước tiên chúng ta phải tìm chuỗi dài nhất, sau đó thêm các ký tự phụ của chuỗi khác.

Đầu vào và Đầu ra

Input:
Two strings. “ABCDEF” and “XYDEF”
Output:
The length of the shortest common super-sequence.
Here the super-sequence is “ABCDEFXY”. So the length is 8.

Thuật toán

superSeq(str1, str2)

Đầu vào: Hai chuỗi str1 và str2.

Đầu ra: Tìm độ dài của siêu dãy.

Begin
   m := length of str1
   n := length of str2
   define table named seqTab of size (m+1 x n+1)

   for i := 0 to m, do
      for j := 0 to n, do
         if i = 0, then
            seqTab[i, j] := j
         else if j = 0, then
            seqTab[i, j] := i
         else if str1[i-1] = str2[j-1], then
            seqTab[i, j] := 1 + seqTab[i-1, j-1]
         else
            seqTab[i, j] := 1 + minimum of seqTab[i-1, j] and seqTab[i, j-1]
      done
   done
   return seqTab[m, n]
End

Ví dụ

#include<iostream>
using namespace std;

int min(int a, int b) {
   return (a<b)?a:b;
}

int superSeq(string str1, string str2) {
   int m = str1.size();
   int n = str2.size();

   int supSeqTable[m+1][n+1];

   for (int i = 0; i <= m; i++) {
      for (int j = 0; j <= n; j++) {
         if (!i)
            supSeqTable[i][j] = j;              //shortest supersequence length is j
         else if (!j)
            supSeqTable[i][j] = i;                //shortest supersequence length is i
         else if (str1[i-1] == str2[j-1])
            supSeqTable[i][j] = 1 + supSeqTable[i-1][j-1];
         else
            supSeqTable[i][j] = 1 + min(supSeqTable[i-1][j], supSeqTable[i][j-1]);
      }
   }
   return supSeqTable[m][n];
}

int main() {
   string first = "ABCDEF";
   string second = "XYDEF";
   cout << "Length of the shortest supersequence is " << superSeq(first, second);
}

Đầu ra

Length of the shortest supersequence is 8