Защищенный пароль

[VladKB1]

Очень надежная и совершенно бесплатная операционная система «Vokna» известна своей безопасностью, так как при проектировании разработчики уделили большое внимание проблемам генерации паролей. Ядро операционной системы содержит в себе строку S длиной N символов. Генерация пароля происходит с использованием символов строки S. Паролем будем называть подстроку Si,j строки S длиной не менее одного и не более N символов. Подстрокой Si,j строки S называется строка, последовательно составленная из символов S[i], S[i+1], S[i+2], … , S[j-1], S[j]. Символы в строке нумеруются последовательно начиная с единицы. Пароль Si,j считается защищенным, если в нем встречается не более K одинаковых символов. Вашей задачей является по заданной строке S и числу K определить количество различных вариантов выбора защищенного пароля. Два варианта выбора пароля S1i,j и S2i’,j’ называются различными, если i ≠ i' или j ≠ j’.

Входные данные

Первая строка входного файла содержит два натуральных числа N (1 ≤ N ≤ 106) и K
(1 ≤ K ≤ N), разделенных одиночным пробелом, где N – количество символов в строке S; K – максимальное количество одинаковых символов в пароле.
Вторая строка входного файла содержит ровно N символов. Каждый символ является либо маленькой латинской буквой, либо цифрой.
Каждая строка входного файла заканчивается символом перевода строки.

Выходные данные

Единственная строка выходного файла должна содержать одно целое число – количество вариантов выбора защищенного пароля.

пример 1

input.txt
6 2
7aaarr

output.txt
15

пример 2

input.txt
4 1
ayay

output.txt
7


У меня вообще не получилось решить задачу. Вот прошу помощи, заранее спасибо!

[Serge_Bliznykov]

На первый взгляд, я бы данную задачу решал банально - простым перебором.
НО!
если я правильно понимаю, то:

Первая строка входного файла содержит два натуральных числа N (1 ≤ N ≤ 106)

N может быть до десять в 6 степении ?!
Если это не опечатка, то хотелось бы посмотреть на строку, длиной в миллион символов!
да и памяти под переменные это потребует не слабо.
я уже молчу о том, что с увеличением строки количество всех возможных вариантов сильно возрастает. Поэтому для простого банального перебора может банально не хватить времени...

Ещё, очевидно,
что все подстроки длиной от 1 до K (включительно) подходят сразу, их можно не проверять.
А вот подстрочки длиной от K+1 до N нужно перебирать

Вы вообще, на каком языке решаете задачу?
Где ваши попытки? Что конкретно вызывает трудности в данной задаче?

p.s. или это очередная попытка решить олимпиадную задачу чужими руками?!

[VladKB1]

Сообщение от Serge_Bliznykov

На первый взгляд, я бы данную задачу решал банально - простым перебором.
НО!
если я правильно понимаю, то:

N может быть до десять в 6 степении ?!
Если это не опечатка, то хотелось бы посмотреть на строку, длиной в миллион символов!
да и памяти под переменные это потребует не слабо.
я уже молчу о том, что с увеличением строки количество всех возможных вариантов сильно возрастает. Поэтому для простого банального перебора может банально не хватить времени...

Ещё, очевидно,
что все подстроки длиной от 1 до K (включительно) подходят сразу, их можно не проверять.
А вот подстрочки длиной от K+1 до N нужно перебирать

Вы вообще, на каком языке решаете задачу?
Где ваши попытки? Что конкретно вызывает трудности в данной задаче?

p.s. или это очередная попытка решить олимпиадную задачу чужими руками?!

Здравствуйте вот фотография задачи это не опечатка http://prntscr.com/673649

Задачу решаю на турбо паскале, и это не попытка решить олимпиадную задачу чужими руками, хотя эта задача с гомельской.обл. олимпиады 2009 года. Я не знаю как описать трудности, а попытки ну я просто не понимаю как это сделать и попыток так таковых и нету, если будет код то я обязательно разберусь! Заранее спасибо!

[Аватар]

1 ≤ N ≤ 106

это не опечатка

Опечатка, должно быть 1 ≤ N ≤ 10^6.

Все ключи длиной от 1 до K, как Сергей заметил, считать без перебора, а просто формулой суммы арифметической прогрессии. При подсчете количества ключей длиннее K трудности видимо в том, что данные ни в строку, ни в массив не удастся засунуть из-за ограничений паскаля. Можно попробовать использовать динамический однонаправленный список и массив-счетчик вхождения символов (их всего 36).

[Poma][a]

Можно попробовать чуть сократить перебор, руководствуясь такими вот мыслями..
Нам не важен порядок.. Нам нужно лишь получить кол-во символов a1, a2, a3, .., am в защищенном(!) пароле.. А дальше по формуле перестановок с повторениями (a1+a2+..+am)!/(a1!*a2!*a3!*..*am!)
Вот..
Поэтому заведем структурку.. char, value.. И устроим рекурсивный перебор.. Осталось еще что-нить придумать..

[FPaul]

Принимаю рассуждения Serge_Bliznykov.
У меня только мысль об оптимизации при проходе на длине m, на (m+1) придётся делать всё заново.
1. Заводим целочисленный массив f[#0...#128].
2. При первом проходе для слова s[1..m] заполняем массив частот f и сразу определяем символ с максимальной частотой. Оцениваем устойчивость пароля.
3. Переходим к следующему слову длиной m s[2..m+1]. При этом вычитаем 1 из элемента массива f, соответствующего букве s[1] и прибавляем к соответствующего s[m+1]. Максимальный элемент ищется среди предыдущего максимума и f[s[m+1]].
Но это не сильно ускорит.

Еще мысль, сделать по типу алгоритма Манакера, но сохранять не длины палиндромов, а повторяющиеся элементы. Но это неоформившаяся мысль.

[VladKB1]

Я сидел 2 с половиной часа и пытался применить всё вами сказанное, но у меня ничего не получилось и я написал полный бред . Будьте добры скиньте код программы. Заранее спасибо!

[FPaul]

Сообщение от VladKB1

Я сидел 2 с половиной часа и пытался применить всё вами сказанное, но у меня ничего не получилось и я написал полный бред . Будьте добры скиньте код программы. Заранее спасибо!

Чудненько. Покажи.

[Smogg]

input.txt
4 1
ayay

output.txt
7

Откуда взялось 7?

У меня всего 4 варианта: a, ay, y, ya.

[Аватар]

Два варианта выбора пароля S1i,j и S2i’,j’ называются различными, если i ≠ i' или j ≠ j’

a y a y ay ya ay