Chuỗi con xuất hiện K lần

View as PDF

Submit solution


Points: 0.47 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Sưu tầm
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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 pirateduyhung123abc 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 \leq N \leq 50000~; ~1 \leq K \leq 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~.

Sample Input

5 2
xxxxx

Sample Output

4

Note

  • Lưu ý: Một chuỗi ~A[1 \dots m]~ được gọi là xuất hiện trong chuỗi ~B[1 \dots n]~ ~K~ lần khi và chỉ khi tồn tại ~K~ vị trí ~i~ phân biệt sao cho ~A[1 \dots m] = B[i \dotsi+m-1]~.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.