DTKSUB - Chuỗi con xuất hiện K lần
Giới hạn- Thời gian: 0.079s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Sau những kỳ công trong những cuộc chinh phục các cấu trúc dữ liệu đặc biệt, tình bạn giữa pirate và duyhung123abc ngày càng trở nên khăng khít. Rồi bỗng một ngày nọ, duyhung123abc bỗng ra đi không một lời từ biệt, chỉ để lại một mẫu giấy cho pirate . Mẩu giấy viết rằng : "Em ơi, anh còn nặng nợ toán lý hóa anh, chưa thể một lòng theo đuổi tin học. Em hãy làm nốt công việc mà anh em ta còn dang dở !" . pirate đọc xong, nước mắt giàn giụa. Nếu khi hai người gặp nhau, vui sướng như khi Engels gặp Marx, thì trong giây phút chia ly này, lòng pirate đau đớn như khi Đỗ Phủ tiễn người tri kỉ Lý Bạch lên đường.
Mất đi người anh cả, pirate như con thuyền mất phương hướng. Cuối cùng, sau những đêm không ngủ, anh quyết định rằng mình sẽ đợi cho đến khi duyhung123abc trả xong nợ công danh và quay trở về sẽ tiếp tục nghiên cứu các cấu trúc dữ liệu đặc biệt. Còn bây giờ, anh ta sẽ đi một con đường mới, đi vào một thế giới mới, thế giới của các THUẬT TOÁN VỀ CHUỖI . Tuy cô độc một mình, nhưng với niềm tin của mình, pirate đã lên đường ngay mà không có chút do dự.
Nhưng trớ trêu thay, vạn sự khởi đầu nan. Thử thách đầu tiên mà con người trẻ tuổi này gặp phải thật đau đầu. Anh ta được cho trước một chuỗi S có độ dài N và một số K. Thử thách được hoàn thành chỉ khi anh ấy đưa ra được độ dài của chuỗi dài nhất xuất hiện ít nhất K lần trong chuỗi S. Làm sao đây ! Vừa vực dậy sau một cú sốc lớn, pirate rất cần sự giúp đỡ của các bạn để không mất đi sự nhiệt huyết của mình !
Input
Dữ liệu vào gồm 2 dòng:
- Dòng 1: Hai số nguyên N và K (1 ≤ N ≤ 50000; 1 ≤ K ≤ 200).
- Dòng 2: Chuỗi S có độ dài N (gồm các chữ cái in thương viết liên tiếp nhau).
Output
Dữ liệu ra gồm một dòng duy nhất là độ dài của chuỗi dài nhất xuất hiện ít nhất K lần trong chuỗi S.
Example
Input: 5 2 xxxxx Output: 4
- Lưu ý: Một chuỗi A[1..m] được gọi là xuất hiện trong chuỗi B[1..n] K lần khi và chỉ khi tồn tại K vị trí i phân biệt sao cho A[1..m] = B[i..i+m-1].
- Người up: khanhptnk
- Nguồn bài: Sưu tầm