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:
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ụ:
KASTR.INP |
KASTR.OUT |
---|---|
7 3 bababab |
4 |
3 1 aaa |
3 |
Giới hạn: