1. Phân tích bài toán
- Yêu cầu: Tìm một xâu con chung có độ dài lớn nhất từ hai xâu và .
- Đặc điểm: Xâu con không cần các ký tự phải đứng liên tiếp nhau nhưng phải giữ đúng thứ tự xuất hiện.
- Kỹ thuật: Sử dụng bảng Quy hoạch động (DP) để lưu trữ độ dài LCS của các tiền tố, sau đó truy vết để tìm xâu kết quả.
2. Ý tưởng thuật toán
Bước 1: Xây dựng bảng DP
- Gọi là độ dài của xâu con chung dài nhất của xâu con và .
- Công thức truy hồi:
- Nếu ký tự tại vị trí tương ứng giống nhau (): .
- Nếu khác nhau (): .
- Cơ sở: và (khi một trong hai xâu rỗng).
Bước 2: Truy vết để tìm xâu kết quả
Sau khi điền đầy bảng , giá trị tại chính là độ dài LCS. Để lấy được xâu cụ thể, ta bắt đầu từ ô cuối cùng và đi ngược về ô :
- Nếu : Ký tự này thuộc LCS. Ta thêm nó vào kết quả và di chuyển chéo lên ô .
- Nếu : Di chuyển sang ô có giá trị lớn hơn giữa và .
- Lặp lại cho đến khi hoặc .
- Lưu ý: Xâu thu được từ việc truy vết sẽ bị ngược, cần đảo ngược lại để có kết quả cuối cùng.
3. Lưu ý khi triển khai
- Kích thước mảng: Với giới hạn , bảng sẽ có khoảng phần tử (kiểu
int). Bộ nhớ tiêu tốn khoảng 36MB, hoàn toàn nằm trong giới hạn cho phép. - C++: Nên khai báo mảng ở phạm vi toàn cục (global) hoặc dùng
std::vector<vector<int>>để tránh tràn bộ nhớ stack. - Python: Do tốc độ xử lý vòng lặp của Python chậm hơn, hãy sử dụng danh sách (list) thay vì các thư viện nặng nề nếu không cần thiết, và chú ý giới hạn đệ quy nếu dùng cách tiếp cận đệ quy có nhớ.
- Truy vết: Khi truy vết, ưu tiên di chuyển theo hướng có giá trị bằng để đảm bảo tính chính xác.