C++ Program: หา Shortest Common Supersequence (SCS) ของ 2 Strings

Shortest Common Supersequence (SCS) คือ String สั้นที่สุดที่มีทั้ง String A และ String B เป็น Subsequence (ไม่ต้องติดกัน แต่ต้องเรียงลำดับเดิม)

ความสัมพันธ์กับ LCS

|SCS| = |A| + |B| - |LCS(A, B)|

หา LCS ก่อน แล้ว Merge โดยใส่ Char ที่ไม่ใช่ LCS เข้าไป

Algorithm: DP + Reconstruction

1. สร้าง DP Table dp[i][j] = ความยาว SCS ของ A[0..i-1] และ B[0..j-1]
2. Recurrence:
   • ถ้า A[i-1] == B[j-1]: dp[i][j] = 1 + dp[i-1][j-1]
   • ถ้าไม่เท่ากัน: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1])
3. Reconstruct: Traceback จาก dp[m][n] สร้าง String

โค้ด C++ สมบูรณ์

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

string shortestCommonSupersequence(const string& A, const string& B) {
    int m = A.length(), n = B.length();
    vector> dp(m + 1, vector(n + 1, 0));
    
    // Build DP Table
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0) dp[i][j] = j;
            else if (j == 0) dp[i][j] = i;
            else 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]);
        }
    }
    
    // Reconstruct SCS from DP Table
    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--;
        }
    }
    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 A = "ABBCDDEEFF";
    string B = "ABCDEEEFF";
    
    string result = shortestCommonSupersequence(A, B);
    cout << "A: " << A << '\n';
    cout << "B: " << B << '\n';
    cout << "Shortest Common Supersequence: " << result << '\n';
    cout << "Length: " << result.length() << '\n';
    
    // Verify: Check both are subsequences
    auto isSubseq = [](const string& sub, const string& super) {
        int i = 0;
        for (char c : super) if (i < sub.size() && c == sub[i]) i++;
        return i == sub.size();
    };
    cout << "A is subsequence: " << (isSubseq(A, result) ? "Yes" : "No") << '\n';
    cout << "B is subsequence: " << (isSubseq(B, result) ? "Yes" : "No") << '\n';
    
    return 0;
}

ผลลัพธ์

A: ABBCDDEEFF
B: ABCDEEEFF
Shortest Common Supersequence: ABBCDEDEEFF
Length: 11
A is subsequence: Yes
B is subsequence: Yes

Trace Example

A = ABBCDDEEFF, B = ABCDEEEFF

LCS = ABCDEEFF (ความยาว 8)

SCS Length = 10 + 9 - 8 = 11

Merge: A[B]B C D D E E F F → Insert B[D]E → ABBCDEDEEFF

Complexity

• Time: O(M × N)
• Space: O(M × N) สำหรับ DP Table (Optimize ได้เป็น O(min(M,N)) ถ้าแค่หาความยาว)

การขยายเป็น Multiple Strings

SCS ของ >2 Strings เป็น NP-Hard ใช้ Heuristics หรือ Approximation Algorithms