Kỳ thi của Trại hè Miền Trung - Tây Nguyên năm 2023 tại trường Trung học Phổ thông chuyên Lê Quý Đôn - Bình Định đã bắt đầu. Nhà vô địch của cuộc thi sẽ được nhận một chú gấu bông rất đẹp.
Ban tổ chức cần đặt một cái tên đẹp cho chú gấu bông này và tên phải liên quan đến chủ đề cho trước:
- Chủ đề là một xâu gồm \(n\) ký tự trong bảng chữ cái tiếng Anh viết thường (từ
a
đếnz
). Tên của chú gấu bông phải là một xâu con của xâu chủ đề. Xâu con của một xâu chính là một dãy các ký tự liên tiếp trong xâu. - Ngoài ra, tên của chú gấu bông còn phải đa dạng, trong tên phải có ít nhất \(k\) ký tự phân biệt.
Các bạn hãy đếm giúp ban tổ chức rằng có bao nhiêu cách chọn xâu con từ xâu chủ đề để đặt tên cho gấu bông, hai cách chọn được coi là khác nhau nếu như vị trí bắt đầu xâu con hoặc vị trí kết thúc của xâu con khác nhau.
Input
- Dòng đầu tiên gồm hai số nguyên dương \(n\) và \(k\) (\(1 \leq n \leq 10^6\), \(1 \leq k \leq 26\)) là độ dài của xâu chủ đề và số lượng ký tự phân biệt tối thiểu của xâu con thoả mãn.
- Dòng thứ hai gồm xâu chủ đề chứa \(n\) ký tự trong bảng chữ cái tiếng Anh viết thường.
Output
- In ra một số nguyên không âm như yêu cầu của đề bài.
Scoring
- Subtask \(1\) (\(16\) điểm): \(k = 1\)
- Subtask \(2\) (\(22\) điểm): \(k = 2\)
- Subtask \(3\) (\(18\) điểm): \(n \leq 10^2\)
- Subtask \(4\) (\(24\) điểm): \(n \leq 10^4\)
- Subtask \(5\) (\(20\) điểm): Không có ràng buộc gì thêm.
Examples
Test 1
Input
14 11
levanthuckkvoi
Output
3
Note
Có \(3\) xâu con gồm levanthuckkvoi
, levanthuckkvo
và evanthuckkvoi
Test 2
Input
9 6
gspvhcute
Output
10
Note
Các ký tự trong xâu đôi một phân biệt nên các xâu con thoả mãn là các xâu con có độ dài lớn hơn hoặc bằng \(6\).
Test 3
Input
6 2
kkkkkk
Output
0
Note
Không tồn tại xâu con nào có ít nhất \(2\) ký tự phân biệt
Test 4
Input
5 2
ngpin
Output
10
Test 5
Input
11 4
fosdethuong
Output
36
Bình luận
Đây là solution, có gì sai sót mong mọi người đóng góp ý kiến nhé. Mình cảm ơn!
https://hackmd.io/@tocbienvaotru/solution_thmttn23p1
Cập nhập python đi ad
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.