Bài 4: KASTR

Một xâu S có độ dài N, thứ tự các kí tự được đánh số từ 1 đến N, xâu S chỉ gồm hai ký tự là ‘a’ và ‘b’. Một xâu con liên tiếp bắt đầu từ L đến R (1 ≤ L ≤ R ≤ N) của S được gọi là xâu con hoàn hảo khi và chỉ khi trong đoạn từ S[L] đến S[R] có chính xác K kí tự ‘a’. Ví dụ, xâu S là “bababab” và K = 3, khi đó S có 4 xâu con hoàn hảo là “bababa”, “ababa”, “bababab”, “ababab” tương ứng các giá trị  (L, R) là (1, 6), (2, 6), (1, 7), (2, 7).

Yêu cầu: Cho xâu S gồm N kí tự và số nguyên K. Đếm xem S có bao nhiêu xâu con hoàn hảo.

Dữ liệu: Vào từ tệp văn bản KASTR.INP có cấu trúc:

•  Dòng đầu chứa hai số nguyên N và K (1 ≤ N ≤ 10⁵, 1 ≤ K ≤ N).
• Dòng thứ hai chứa xâu S (chỉ gồm hai ký tự ‘a’ và ‘b’).

Kết quả: Ghi ra tệp văn bản KASTR.OUT một số nguyên duy nhất là số lượng xâu con hoàn hảo của S.

Ví dụ:

 Giới hạn:

• Có 30% số test tương ứng 30% số điểm có N ≤ 100.
• Có 30% số test khác tương ứng 30% số điểm có N ≤ 1000.
• 40% số test còn lại tương ứng 40% số điểm có N ≤ 10⁵.