|
Почти палиндром
(Время: 1 сек. Память: 16 Мб Сложность: 40%)
Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".
Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).
Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).
Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.
Входные данные
В первой строке входного файла INPUT.TXT вводятся два натуральных числа: N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N). Во второй строке записано слово S, состоящее из N строчных английских букв.
Выходные данные
В выходной файл OUTPUT.TXT требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5 1
abcde | 12 |
| 2 | 3 3
aaa | 6 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
