Trước kỳ thi VOI, Tèo đã thực hiện một nghiên cứu và phát hiện ra rằng một chuỗi con gồm bazơ liên tiếp trên một đoạn chuỗi DNA có liên quan đến tỉ lệ AC (Accepted) khi giải bài! Vì vậy, Tèo muốn nghiên cứu mối quan hệ này.
Cụ thể, cho một chuỗi DNA, hãy giúp Tèo tìm ra số lần xuất hiện của chuỗi con (gồm bazơ liên tiếp) xuất hiện nhiều nhất trong chuỗi DNA đã cho.
Dữ liệu:
Dòng đầu tiên là một chuỗi DNA. Đảm bảo chuỗi DNA hợp lệ, tức là chỉ chứa bốn loại bazơ A, G, C, T.
Dòng thứ hai là một số nguyên dương , có ý nghĩa như trong mô tả đề bài.
Kết quả: In ra một dòng chứa một số nguyên dương duy nhất là câu trả lời cho bài toán.
Ví dụ:
Dữ liệu:
AAAAA
1
Kết quả:
5
Dữ liệu:
ACTCACTC
4
Kết quả:
2
Giới hạn: Ký hiệu độ dài chuỗi DNA là . Dữ liệu đảm bảo .
