Tổng quan
Bài toán Chuỗi Con Chung Dài Nhất (LCS) tìm dãy ký tự dài nhất xuất hiện trong cả hai chuỗi đầu vào theo cùng thứ tự tương đối, nhưng không nhất thiết liền kề. Đây là ví dụ kinh điển của quy hoạch động, khi một bảng DP hai chiều cho phép ta tái sử dụng lời giải của các bài toán con chồng lấp thay vì giải lại từ đầu.
Bằng cách điền một bảng mà ô dp[i][j] lưu độ dài LCS của i ký tự đầu chuỗi này và j ký tự đầu chuỗi kia, thuật toán giải toàn bộ bài toán trong O(m·n) — cải tiến khổng lồ so với đệ quy ngây thơ theo cấp số mũ. LCS là nền tảng cho các công cụ như diff và việc gộp (merge) trong quản lý phiên bản.
Dãy con chung dài nhất (LCS) hoạt động thế nào?
- Tạo bảng DP kích thước (m+1)×(n+1) và khởi tạo hàng đầu và cột đầu bằng 0 — tiền tố rỗng không có chuỗi con chung nào.
- Điền bảng theo từng hàng, so sánh ký tự i của chuỗi thứ nhất với ký tự j của chuỗi thứ hai.
- Nếu hai ký tự khớp, đặt dp[i][j] = dp[i-1][j-1] + 1 — mở rộng bài toán con theo đường chéo thêm một.
- Nếu khác nhau, lấy phương án tốt hơn giữa việc bỏ một ký tự ở mỗi chuỗi: dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
- Ô dưới cùng bên phải chứa độ dài LCS; truy vết ngược qua bảng để khôi phục chuỗi con thực tế.
Khi nào nên dùng?
- Là lõi của các tiện ích diff và việc gộp mã nguồn, làm nổi bật phần chung của hai phiên bản tệp.
- Tin sinh học — đo độ tương đồng giữa các chuỗi DNA, RNA hoặc protein.
- Phát hiện đạo văn và so khớp văn bản mờ, khi phần nội dung trùng lặp là quan trọng.
- Làm khối xây dựng cho các độ đo dựa trên chỉnh sửa liên quan, như mô hình dòng của diff/patch.
Phân tích độ phức tạp
Việc điền mọi ô của bảng (m+1)×(n+1) tốn O(m·n) thời gian và O(m·n) bộ nhớ ở phiên bản trực tiếp. Vì mỗi hàng chỉ phụ thuộc hàng trước đó, có thể giảm bộ nhớ xuống O(min(m,n)) bằng cách chỉ giữ hai hàng — nhưng đánh đổi này khiến việc khôi phục chính chuỗi con trở nên khó hơn.
Câu hỏi thường gặp
Khác biệt giữa chuỗi con (subsequence) và chuỗi con liên tiếp (substring) là gì?
Substring phải liền kề, còn subsequence chỉ cần giữ đúng thứ tự tương đối của các ký tự và có thể bỏ qua ký tự khác. 'ace' là subsequence của 'abcde' nhưng không phải substring.
Vì sao quy hoạch động nhanh hơn đệ quy ngây thơ ở bài này?
Đệ quy ngây thơ giải lại cùng những bài toán con chồng lấp vô số lần theo cấp số mũ. Bảng DP lưu lời giải mỗi bài toán con đúng một lần, nên tổng công việc giảm còn O(m·n) ô phân biệt.
Có thể có nhiều hơn một chuỗi con chung dài nhất không?
Có. Nhiều chuỗi con có thể cùng đạt độ dài lớn nhất; DP cho độ dài duy nhất, nhưng bước truy vết có thể chọn một trong nhiều đáp án dài bằng nhau tùy cách xử lý hòa.