Chuỗi con chung ngắn nhất (Shortest Common Super Sequence)

Giới thiệu

Chuỗi con chung ngắn nhất (Shortest Common Supersequence - SCS) là một chuỗi mà trong đó mỗi phần tử của cả hai chuỗi cho trước đều xuất hiện. Nói cách khác, cả hai chuỗi đã cho đều là chuỗi con của chuỗi Super chung ngắn nhất.

Khi hai chuỗi không có ký tự chung nào, ta chỉ cần nối chúng lại để được Super-chuỗi. Nhưng khi chúng có một số ký tự chung, trước tiên ta phải tìm chuỗi con chung dài nhất (LCS), sau đó thêm các ký tự thừa của chuỗi kia vào.

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

Đầu vào: Hai chuỗi "ABCDEF" và "XYDEF"
Đầu ra: Độ dài của chuỗi con chung ngắn nhất. Ở đây super-chuỗi là "ABCDEFXY". Do đó độ dài là 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 super chuỗi.

Begin
    m := độ dài của str1
    n := độ dài của str2
    định nghĩa bảng seqTab kích thước (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 + min(seqTab[i-1, j], seqTab[i, j-1])
        done
    done
    return seqTab[m, n]
End

Ví dụ (C++)

#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;  // độ dài superchuỗi ngắn nhất là j
            else if (!j)
                supSeqTable[i][j] = i;  // độ dài superchuỗi ngắn nhất là 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);
}

Kết quả

Length of the shortest supersequence is 8