Các cá thể được tạo ra bằng công nghệ biến đổi gen khi đưa ra nhân giống đại trà bằng phương pháp
sinh sản hữu tính dần dần mất đi một số đặc tính quý báu có ở các thế hệ ban đầu. Vấn đề ở chổ là
các cá thể thế hệ mới không giữ được trọn vẹn các gen quý của bố và mẹ. Bản đồ gen của mỗi cá
thể được biểu diễn dưới dạng xâu ký tự chỉ chứa các ký tự Latinh in thường, mỗi ký tự đại diện
cho một gen. Nếu bản đồ gen của mẹ/bố là , (cá thể thế hệ ) và bản đồ gen của con sinh ra trực tiếp từ cá
thể này (thế hệ ) là thì có các tính chất sau:
- có ký tự đầu giống ký tự đầu của .
- có ký tự cuối giống ký tự cuối của .
Nói một cách khác có tiền tố độ dài trùng khớp với tiền tố độ dài của và có hậu tố độ dài trùng khớp với hậu tố độ dài của . Nếu là giá trị lớn nhất của các thỏa mãn hai điều kiện trên thì cặp bản đồ và có "độ ổn định di truyền k". Trên cánh đồng thực nghiệm hiện có cây đánh số từ đến , cây thứ có bản đồ gen là , . Người ta cần chọn một cặp cá thể có độ ổn định di truyền để nghiên cứu. Hãy xác định – số cặp khác nhau có thể lựa chọn. Hai cặp gọi là khác nhau nếu tồn tại một cây có ở cặp này và không có ở cặp kia.
Dữ liệu
Vào từ tệp dữ liệu chuẩn:
- Dòng đầu tiên chứa hai số nguyên và .
- Dòng thứ trong dòng sau chứa xâu , mỗi xâu có độ dài không quá .
Kết quả
Đưa ra thiết bị xuất chuẩn một số nguyên .
Ví dụ
Dữ liệu:
Copy
5 2
aaaaaa
aabdecaa
aaaa
bbcaa
bbaaehaa
Kết quả:
Copy
3
Subtask
số test có .
số test có .
Comments