C++: Tìm dãy con chung dài nhất (LCS) của tập hợp nhiều chuỗi

Longest Common Subsequence (LCS) của một tập chuỗi là chuỗi dài nhất xuất hiện dưới dạng subsequence (giữ thứ tự, không cần liên tiếp) trong tất cả các chuỗi của tập hợp.

Lưu ý: Bài viết gốc nhầm lẫn giữa Longest Common Prefix (tiền tố chung) và Longest Common Subsequence (dãy con chung). Dưới đây là giải pháp đúng cho LCS của nhiều chuỗi.

Độ phức tạp

• LCS của 2 chuỗi: DP O(m*n).
• LCS của k chuỗi: NP-hard khi k không cố định.
• Với k nhỏ (≤ 10) và độ dài vừa (≤ 100), có thể dùng DP đa chiều hoặc quy hoạch động trên bitmask.

Giải pháp cho 2 chuỗi (cơ sở)

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]);
    
    // Truy vết
    string res;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i-1] == B[j-1]) { res.push_back(A[i-1]); --i; --j; }
        else if (dp[i-1][j] > dp[i][j-1]) --i;
        else --j;
    }
    reverse(res.begin(), res.end());
    return res;
}

Mở rộng cho k chuỗi (k nhỏ, độ dài nhỏ)

Sử dụng DP trên trạng thái là vector chỉ số (i1, i2, ..., ik). Số trạng thái = tích độ dài các chuỗi → chỉ khả thi khi tích nhỏ (ví dụ 5 chuỗi độ dài ≤ 10).

Heuristic thực tế: LCS cặp lặp

Tính LCS của 2 chuỗi đầu, sau đó tính LCS của kết quả với chuỗi thứ 3, v.v. Kết quả là một LCS của tập hợp (không đảm bảo là dài nhất tuyệt đối nhưng thường đủ tốt).

string lcsMultiple(vector& strs) {
    if (strs.empty()) return "";
    string res = strs[0];
    for (size_t i = 1; i < strs.size(); ++i)
        res = lcs2(res, strs[i]);
    return res;
}

Chương trình minh họa (LCS 2 chuỗi)

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

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]);
    
    string res;
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (A[i-1] == B[j-1]) { res.push_back(A[i-1]); --i; --j; }
        else if (dp[i-1][j] > dp[i][j-1]) --i;
        else --j;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    vector seqs = {"Tutorialspoint", "Tutor", "Tutorials"};
    // Heuristic: LCS cặp lặp
    string res = seqs[0];
    for (size_t i = 1; i < seqs.size(); ++i)
        res = lcs2(res, seqs[i]);
    
    cout << "LCS (heuristic) cua tap chuoi: " << res << '\n';
    // Kết quả: "Tutor" (cùng với LCP trong trường hợp này)
    return 0;
}

Kết quả

LCS (heuristic) cua tap chuoi: Tutor

Phân biệt LCP vs LCS

Nếu bài toán yêu cầu tiền tố chung (prefix), hãy dùng thuật toán O(S) đơn giản (xem bài 1003082295). Nếu yêu cầu dãy con chung (subsequence) cho nhiều chuỗi, hãy cân nhắc heuristic hoặc giới hạn đầu vào nhỏ.