Xâu con chung dài nhất (LCS) và truy vết khôi phục chuỗi

Mục tiêu kiến thức

• Nắm vững công thức quy hoạch động LCS trên 2 chuỗi ký tự O(N × M).
• Cài đặt kỹ thuật truy vết ngược từ bảng DP để khôi phục cấu trúc xâu con chung dài nhất.
• Hiểu cách tối ưu hóa bộ nhớ và xử lý dữ liệu xâu trong C++.

Mô tả bài toán

Trong hệ thống đối soát phiên bản mã nguồn của AI Empire Academy, công cụ diff cần tìm chuỗi chỉ thị chung dài nhất giữa hai bản thảo thuật toán để xác định phần mã không bị thay đổi. Cho hai chuỗi ký tự S₁ và S₂ chỉ gồm các chữ cái in hoa tiếng Anh ('A' đến 'Z').

Một chuỗi S được gọi là chuỗi con (subsequence) của S₁ nếu có thể thu được S bằng cách xóa đi một số (hoặc không xóa) ký tự từ S₁ mà không làm thay đổi thứ tự tương đối của các ký tự còn lại.

Nhiệm vụ của bạn là:

• Tìm độ dài của xâu con chung dài nhất (LCS) của S₁ và S₂.
• Khôi phục và in ra xâu con chung đó theo quy tắc truy vết chuẩn sau:
• Xuất phát từ ô (N, M) của bảng dp, lùi về (0, 0).
• Nếu S₁[i-1] == S₂[j-1], ký tự này thuộc LCS, lùi về (i-1, j-1).
• Ngược lại nếu dp[i-1][j] ≥ dp[i][j-1], lùi về (i-1, j).
• Ngược lại, lùi về (i, j-1).
• Đảo ngược chuỗi ký tự thu được để có xâu kết quả.

Quy ước nộp bài

• Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
• Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
• Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
• Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Ràng buộc

• 1 ≤ |S₁|, |S₂| ≤ 2000.
• Thời gian chạy: 1000ms.
• Bộ nhớ tối đa: 256MB.