Tên hay

Xem PDF



Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, JS, Lua, Node JS, ObjectiveC, Pascal, Prolog, Scala
Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: DRX02T1.inp Output: DRX02T1.out

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 đến z). 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\)\(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

\(3\) xâu con gồm levanthuckkvoi, levanthuckkvoevanthuckkvoi

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