C++: Tìm Supersequence ngắn nhất chứa 2 chuỗi (Shortest Common Supersequence)

Shortest Common Supersequence (SCS) của hai chuỗi A và B là chuỗi ngắn nhất mà cả A và B đều là subsequence (dãy con không cần liên tiếp) của nó.

Mối quan hệ với LCS

Độ dài SCS = |A| + |B| - |LCS(A, B)|. Ta có thể xây dựng SCS từ bảng DP của LCS.

Thuật toán Dynamic Programming

1. Xây bảng dp[i][j] = độ dài SCS của A[0..i-1] và B[0..j-1].
2. Cơ sở: dp[0][j] = j, dp[i][0] = i.
3. Chuyển trạng thái:
   • Nếu A[i-1] == B[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
   • Khác: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
4. Truy vết (traceback) từ dp[m][n] để xây chuỗi SCS.

Chương trình hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

string shortestCommonSupersequence(string A, string B) {
    int m = A.size(), n = B.size();
    vector> dp(m + 1, vector(n + 1, 0));
    
    // Khởi tạo cơ sở
    for (int i = 0; i <= m; ++i) dp[i][0] = i;
    for (int j = 0; j <= n; ++j) dp[0][j] = j;
    
    // Điền bảng DP
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (A[i-1] == B[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]);
        }
    }
    
    // Truy vết xây chuỗi SCS
    string scs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i-1] == B[j-1]) {
            scs.push_back(A[i-1]);
            --i; --j;
        } else if (dp[i-1][j] < dp[i][j-1]) {
            scs.push_back(A[i-1]);
            --i;
        } else {
            scs.push_back(B[j-1]);
            --j;
        }
    }
    // Thêm phần còn lại
    while (i > 0) scs.push_back(A[--i]);
    while (j > 0) scs.push_back(B[--j]);
    
    reverse(scs.begin(), scs.end());
    return scs;
}

int main() {
    string M = "ABBCDDEEFF";
    string N = "ABCDEEEFF";
    cout << "SCS cua \"" << M << "\" va \"" << N << "\" la: " 
         << shortestCommonSupersequence(M, N) << '\n';
    return 0;
}

Kết quả

SCS cua "ABBCDDEEFF" va "ABCDEEEFF" la: ABBCDEDEEFF

Giải thích kết quả

A = A B B C D D E E F F
B = A B C D E E E F F
SCS = A B B C D E D E E F F
      ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
      A B   C D   E   F F  (các ký tự chung - LCS)
      B     D     E       (ký tự thêm từ A/B)

Độ phức tạp

• Thời gian: O(m * n)
• Không gian: O(m * n) (có thể tối ưu thành O(min(m,n)) nếu chỉ cần độ dài).

Mở rộng

• Để in tất cả SCS (có thể nhiều), dùng backtracking trên bảng DP.
• Cho k chuỗi: NP-hard (không có thuật toán đa thức trừ khi k cố định nhỏ).
• Ứng dụng: nén dữ liệu, so sánh gene (bioinformatics), diff tool.

SCS là bài toán cổ điển của DP trên chuỗi, biến thể tự nhiên của LCS (Longest Common Subsequence).