Độ đẹp của xâu

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Python 1.5s
Bộ nhớ:
Python 64M
Tác giả:
jumptozero
Dạng bài
Điểm: 250 Thời gian: 0.2s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho xâu \(S\) có độ dài \(n\) và một số nguyên \(k(1\le k\le n)\). Xâu \(S\) có "độ đẹp" là \(x\), nếu \(x\) là số nguyên không âm lớn nhất thỏa mãn:

  • Trong \(S\) tồn tại \(x\) xâu con (gồm những phần tử liên tiếp) có độ dài là \(k\) và chúng không được chồng lên nhau

  • Tất cả các phần tử của \(x\) xâu con này phải giống nhau.

Yêu cầu: Cho số nguyên \(k\) và xâu \(S\) có độ dài là \(n\). Tìm "độ đẹp" của \(S\)

Input

  • Dòng thứ nhất chứa hai số nguyên \(n\) và \(k(1\le k\le n\le 2.10^5)\)

  • Dòng thứ hai chứa xâu \(S\) có độ dài là \(n\)

Output

  • In ra đáp án cần tìm

Example

Test 1

Input 
4 2
aabb
Output 
1
Note

Ở ví dụ 1: Xâu \("aabb"\) có "độ đẹp" là \(1\) vì chỉ có tối đa \(1\) xâu con có độ dài là \(2\) mà tất cả các phần tử của chúng giống nhau!

Test 2

Input 
7 2
aabbbaa
Output 
2
Note

Ở ví dụ 2: Xâu \("aabbbaaa"\) có độ đẹp là \(2\) vì có \(2\) xâu con \("aa"\) xuất hiện trong \("aabbbaa"\)

Bình luận


  • 6
    jumptozero    9:12 a.m. 26 Tháng 7, 2020 ← đã chỉnh sửa

    Mình đã edit lại bộ test ,các bạn sub lại nhé ! Do bộ test trên mình sinh kết quả toàn băng 0 !


    • -27
      ap    2:41 p.m. 1 Tháng 7, 2021

      Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

      2 bình luận nữa