Elearning CodePath – CTP Online Judge

Khôi phục chuỗi DNA (String Reconstruction)

RECONSTRUCT

🟢 Easy #Graph

### Bài toán
Trong công nghệ giải trình tự gene, các máy giải trình tự hiện đại không thể đọc toàn bộ một sợi DNA dài mà chỉ có thể đọc được các đoạn ngắn gọi là k-mers.

Cho một tập hợp các chuỗi con (substring) có độ dài k (k-mers). Giả sử rằng các k-mers này bao phủ toàn bộ chuỗi gốc và mỗi k-mer xuất hiện đúng một lần trong quá trình giải trình tự.

Yêu cầu: Hãy tìm một chuỗi gốc ngắn nhất sao cho chuỗi đó chứa tất cả các k-mers đã cho theo đúng thứ tự xuất hiện. Biết rằng hai k-mers kế tiếp nhau trong chuỗi gốc sẽ chồng lấp (overlap) lên nhau k-1 ký tự.

Ví dụ: Với các k-mers {ABC, BCD, CDE}, chuỗi gốc sẽ là ABCDE.

### Định dạng Đầu vào
Dữ liệu vào từ file RECONSTRUCT.INP:
- Dòng đầu tiên chứa số nguyên N (số lượng k-mers) và K (độ dài mỗi k-mer).
- N dòng tiếp theo, mỗi dòng chứa một chuỗi k-mer.

### Định dạng Đầu ra
Ghi ra file RECONSTRUCT.OUT:
- Một dòng duy nhất chứa chuỗi gốc đã được khôi phục. Nếu có nhiều kết quả có cùng độ dài nhỏ nhất, hãy in ra chuỗi có thứ tự từ điển nhỏ nhất.

### Ví dụ
| Input | Output |
| :--- | :--- |
| 3 3 | ABCDE |
| ABC | |
| BCD | |
| CDE | |

### Subtasks
- Subtask 1 (40%): N <= 10, K <= 5.
- Subtask 2 (60%): N <= 10^5, K <= 100.

✅ Đã AC: 1 / 8 submissions