C++ Program: Longest Common Subsequence (LCS) ของหลาย Sequences

Longest Common Subsequence (LCS) คือ Subsequence ที่ยาวที่สุดที่ปรากฏในทุก Sequence ของชุดที่กำหนด (Subsequence = เก็บลำดับแต่ไม่ต้องติดกัน)

ข้อสังเกตสำคัญ

บทความต้นฉบับมี Title ว่า "Longest Subsequence Common to All Sequences" แต่โค้ดตัวอย่างทำ Longest Common Prefix ไม่ใช่ LCS จริง (Prefix ต้องเริ่มต้นที่ Index 0, Subsequence ไม่จำเป็น)

LCS จริงของ 2 Strings (Standard DP)

string lcs2(const string& A, const string& B) {
    int m = A.size(), n = B.size();
    vector> dp(m+1, vector(n+1, 0));
    
    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] = max(dp[i-1][j], dp[i][j-1]);
    
    // Reconstruct
    string lcs;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i-1] == B[j-1]) {
            lcs.push_back(A[i-1]);
            i--; j--;
        } else if (dp[i-1][j] > dp[i][j-1]) i--;
        else j--;
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

LCS ของ Multiple Strings (k Strings)

Generalization เป็น NP-Hard สำหรับ k ที่ไม่คงที่ แต่ถ้า k คงที่และเล็ก ใช้ DP หลายมิติได้

3 Strings: O(N³) DP

string lcs3(const string& A, const string& B, const string& C) {
    int a = A.size(), b = B.size(), c = C.size();
    vector>> dp(a+1, vector>(b+1, vector(c+1, 0)));
    
    for (int i = 1; i <= a; i++)
        for (int j = 1; j <= b; j++)
            for (int k = 1; k <= c; k++)
                if (A[i-1] == B[j-1] && B[j-1] == C[k-1])
                    dp[i][j][k] = 1 + dp[i-1][j-1][k-1];
                else
                    dp[i][j][k] = max({dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1]});
    
    // Reconstruct (ซับซ้อนกว่า 2 Strings)
    // ...
    return ""; // Implementation omitted for brevity
}

Longest Common Prefix (สิ่งที่โค้ดต้นฉบับทำจริง)

ถ้าต้องการแค่ Prefix (ขึ้นต้นเดียวกัน) ใช้วิธี Horizontal Scanning (ดูบทความก่อนหน้า)

Heuristic สำหรับ Multiple Strings LCS

1. หา LCS ของ Pair แรก → ได้ Candidate
2. Filter Candidate กับ String ถัดไป
3. ทำซ้ำจนครบทุก String

ไม่ Guarantee Optimal แต่เร็วและ Practical

โค้ดต้นฉบับ (Common Prefix) - 修正版

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

string commonPrefix(const string& s1, const string& s2) {
    int i = 0, n = min(s1.size(), s2.size());
    while (i < n && s1[i] == s2[i]) i++;
    return s1.substr(0, i);
}

string longestCommonPrefix(vector& strs) {
    if (strs.empty()) return "";
    string prefix = strs[0];
    for (size_t i = 1; i < strs.size(); i++) {
        prefix = commonPrefix(prefix, strs[i]);
        if (prefix.empty()) break;
    }
    return prefix;
}

int main() {
    vector arr = {"Tutorialspoint", "Tutor", "Tutorials"};
    string result = longestCommonPrefix(arr);
    cout << (result.empty() ? "No common prefix" : "Longest common prefix: " + result) << '\n';
    return 0;
}

ผลลัพธ์

Longest common prefix: Tutor

สรุปความแตกต่าง