Khóa học Python từ Cơ bản đến Nâng cao

Bài 10.3 - Cài đặt Longest Common Subsequence (LCS) bằng Python

LCS (Longest Common Subsequence) là một bài toán cực kỳ phổ biến trong lĩnh vực xử lý chuỗi, được ứng dụng nhiều trong so sánh văn bản, DNA, diff file, v.v.

Mục tiêu

Cho hai chuỗi X và Y, tìm độ dài chuỗi con chung dài nhất mà giữ đúng thứ tự các ký tự, nhưng không cần liên tiếp.

Ví dụ

Input:
X = "abcde"
Y = "ace"

Output:
LCS = "ace"
Độ dài = 3

1. Ý tưởng giải bằng Quy hoạch động

• Sử dụng bảng 2 chiều dp[i][j]: độ dài LCS của X[:i] và Y[:j]
• Nếu X[i-1] == Y[j-1] ⇒ dp[i][j] = dp[i-1][j-1] + 1
• Ngược lại ⇒ dp[i][j] = max(dp[i-1][j], dp[i][j-1])

2. Cài đặt hàm tính độ dài LCS

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]

    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Ví dụ sử dụng:

X = "abcde"
Y = "ace"
print("Độ dài LCS:", lcs_length(X, Y))  # Output: 3

Bảng dp giúp ta tránh lặp lại tính toán như trong đệ quy.

3. Cách in ra chuỗi LCS thực tế

def get_lcs_string(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n+1) for _ in range(m+1)]

    # Tính bảng dp như trước
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    # Truy ngược để tìm chuỗi
    i, j = m, n
    lcs = []

    while i > 0 and j > 0:
        if X[i-1] == Y[j-1]:
            lcs.append(X[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(lcs))

Ví dụ:

X = "abcde"
Y = "ace"
print("Chuỗi LCS:", get_lcs_string(X, Y))  # Output: ace

Truy ngược từ dp[m][n] giúp khôi phục chuỗi đúng thứ tự.

4. Độ phức tạp thuật toán

• Có thể tối ưu bộ nhớ thành O(n) nếu chỉ cần độ dài (không cần in chuỗi)

5. Mở rộng và ứng dụng

• So sánh tài liệu (diff tool)
• Tìm chuỗi con chung trong chuỗi ADN
• Gộp thay đổi file trong Git (merge conflict)
• Đánh giá độ tương đồng giữa 2 đoạn văn

Tổng kết

• LCS là bài toán kinh điển giúp rèn tư duy quy hoạch động 2 chiều.
• Học LCS là bước đệm để học các bài nâng cao hơn như Edit Distance, LCS 3 chuỗi, v.v.
• Khi làm bài, đừng quên kiểm tra chỉ số và hiểu rõ công thức cập nhật dp.