Khôi phục DNA
Đề bài
Mô tả
Trong tin sinh học, các nhà khoa học thường nghiên cứu DNA thông qua những đoạn ngắn có cùng độ dài, gọi là các -mer. Một xâu DNA là xâu chỉ gồm bốn ký tự A, C, G và T.
Một xâu DNA có độ dài sinh ra xâu con liên tiếp độ dài , bắt đầu tại các vị trí . Ví dụ, với , xâu ACGTA sinh ra ba -mer: ACG, CGT và GTA.
Sau một thí nghiệm giải trình tự, các nhà khoa học thu được đoạn DNA đôi một phân biệt , mỗi đoạn có độ dài đúng bằng . Họ muốn khôi phục một xâu DNA ngắn nhất từ các đoạn này.
Một xâu DNA được gọi là hợp lệ nếu thỏa mãn cả hai điều kiện sau:
- mọi () xuất hiện ít nhất một lần dưới dạng xâu con liên tiếp của ;
- mọi xâu con liên tiếp độ dài của đều thuộc tập .
Như vậy, một đoạn có thể xuất hiện trong nhiều lần, nhưng không được có -mer nào nằm ngoài danh sách đã cho xuất hiện trong .
Ngoài ra, do giới hạn lưu trữ, độ dài của không được vượt quá
trong đó là một số nguyên không âm cho trước.
Hãy tìm độ dài nhỏ nhất của một xâu DNA hợp lệ có độ dài không vượt quá giới hạn trên. Nếu không tồn tại xâu như vậy, in ra .
Dữ liệu vào
- Dòng đầu tiên chứa ba số nguyên , và (, , ).
- Dòng thứ trong dòng tiếp theo chứa xâu có độ dài đúng bằng và chỉ gồm các ký tự A, C, G và T.
Các xâu đôi một phân biệt.
Dữ liệu ra
In ra một số nguyên: độ dài nhỏ nhất của một xâu DNA hợp lệ có độ dài không quá , hoặc nếu không tồn tại xâu như vậy.
Ràng buộc
- .
- .
- .
- Mỗi có độ dài , chỉ gồm A, C, G, T; các đôi một phân biệt.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 5 2 1 AC AG AT CG GA |
7 | Xâu ACGAGAT có độ dài và chứa cả năm đoạn đã cho; đoạn GA xuất hiện trong nó hai lần. Không có xâu hợp lệ nào độ dài . |
| 5 2 0 AC AG AT CG GA |
-1 | Cần ít nhất ký tự để tạo được một xâu hợp lệ, trong khi giới hạn độ dài là . |
| 2 3 9 ACT GGA |
-1 | Không có xâu nào chứa được cả hai đoạn đã cho mà không chứa thêm một -mer nằm ngoài danh sách. |
Bình luận