In tất cả xâu con chung dài nhất theo thứ tự từ điển trong C++

Giới thiệu

Cho 2 xâu str1, str2. Tìm và in tất cả các xâu con chung dài nhất (LCS - Longest Common Subsequences) theo thứ tự từ điển.

Ví dụ

str1 = "xysxysx", str2 = "xsyxsyx"

LCS length = 5

Các LCS theo thứ tự từ điển:

xsxsx
xsxyx
xsysx
xysyx
xyxsx
xyxyx

Thuật toán

1. Tính độ dài LCS bằng DP (Dynamic Programming)
2. Duyệt theo thứ tự từ điển (a-z), xây dựng xâu con
3. Tại mỗi bước, tìm ký tự tiếp theo có thể dẫn đến LCS đủ độ dài
4. Sử dụng memoization (DP table) để kiểm tra nhanh

Mã nguồn hoàn chỉnh

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

const int MAX = 100;
int dp[MAX][MAX];

// Tính độ dài LCS từ vị trí (i,j)
int lcsLength(string &s1, string &s2, int i, int j) {
    if (i == s1.length() || j == s2.length()) return 0;
    int &res = dp[i][j];
    if (res != -1) return res;
    
    if (s1[i] == s2[j]) 
        res = 1 + lcsLength(s1, s2, i + 1, j + 1);
    else 
        res = max(lcsLength(s1, s2, i + 1, j), 
                  lcsLength(s1, s2, i, j + 1));
    return res;
}

// In tất cả LCS theo thứ tự từ điển
void printAllLCS(string &s1, string &s2, int i, int j, string &cur, int targetLen) {
    if (cur.length() == targetLen) {
        cout << cur << endl;
        return;
    }
    if (i == s1.length() || j == s2.length()) return;
    
    // Thử các ký tự từ 'a' đến 'z'
    for (char ch = 'a'; ch <= 'z'; ch++) {
        bool found = false;
        for (int x = i; x < s1.length(); x++) {
            if (s1[x] == ch) {
                for (int y = j; y < s2.length(); y++) {
                    if (s2[y] == ch && lcsLength(s1, s2, x, y) == targetLen - cur.length()) {
                        cur.push_back(ch);
                        printAllLCS(s1, s2, x + 1, y + 1, cur, targetLen);
                        cur.pop_back();
                        found = true;
                        break;
                    }
                }
                if (found) break;
            }
        }
        if (found) break; // Quan trọng: chỉ lấy ký tự nhỏ nhất có thể tại mỗi vị trí
    }
}

int main() {
    string str1 = "xysxysx";
    string str2 = "xsyxsyx";
    
    memset(dp, -1, sizeof(dp));
    int lcsLen = lcsLength(str1, str2, 0, 0);
    
    cout << "Do dai LCS: " << lcsLen << endl;
    cout << "Tat ca LCS theo thu tu tu dien:" << endl;
    
    string current = "";
    printAllLCS(str1, str2, 0, 0, current, lcsLen);
    
    return 0;
}

Kết quả chạy chương trình

Do dai LCS: 5
Tat ca LCS theo thu tu tu dien:
xsxsx
xsxyx
xsysx
xysyx
xyxsx
xyxyx

Phân tích độ phức tạp

• Tính LCS length: O(n×m) time, O(n×m) space
• In tất cả LCS: O(k × n × m) - k = số lượng LCS
• Trong trường hợp xấu, số LCS có thể mũ (exponential)

Lưu ý quan trọng

• Code chỉ hoạt động đúng cho chữ cái thường 'a'-'z'. Cần mở rộng cho ASCII đầy đủ.
• Điều kiện break sau khi tìm thấy ký tự hợp lệ đảm bảo thứ tự từ điển.
• DP table dp[i][j] lưu LCS length từ (i,j) đến cuối.

Kết luận

In tất cả LCS theo thứ tự từ điển là bài toán nâng cao của LCS, kết hợp DP + backtracking có thứ tự. Ứng dụng trong so sánh phiên bản văn bản, bioinformatics (DNA alignment).