Мюллер давно подозревал, что Штирлиц периодически отсылает шифровки в СССР.
И вот, наконец, он почти поймал его за руку: роясь в бумагах Штирлица, он
нашёл непонятный набор цифр, записанный на чистом листе. Сразу догадавшись,
что это шифровка, он вызвал Штирлица на допрос. Тот же невозмутимо
объяснил, что это всего лишь номер лотерейного билета, который он переписал
на лист бумаги, чтобы не забыть. Штирлиц никогда не был так близок к
провалу — ведь на листе были записаны координаты бункера Гитлера.
Для передачи этих данных в Центр Штирлиц использовал следующий алгоритм:
- На вход подаётся строка s =
s1s2…sn.
- Выбирается ключ k — целое положительное число, строго меньшее n.
- Для каждого символа строки si выполняется следующая процедура:
- Рассматривается строка qi, состоящая из
k подряд идущих символов строки s, начиная с i-го:
qi = sisi + 1…si + k − 1.
Если до конца строки не набирается k символов, то оставшиеся символы
берутся из начала строки:
qi = si…sns1…si + k − 1 − n.
- Для строки qi подсчитывается количество
различных непустых её подстрок — mi.
- Последовательность m1, m2, …,
mn выдаётся в качестве ответа.
Шифровать этим алгоритмом не так уж просто, а как потом это расшифровывать,
вообще известно только советской разведке. Вам предоставляется шанс на
несколько минут почувствовать себя Штирлицем.
Исходные данные
В первой строке записан ключ k, 1 ≤ k ≤ 1000.
Вторая строка содержит строку s, которую вам предстоит зашифровать.
Строка состоит из строчных латинских букв, её длина строго больше k и не превосходит 4000.
Результат
Выведите числа m1, m2, …,
mn, разделённые пробелами.
Пример
исходные данные | результат |
---|
3
abaccc
| 5 6 5 3 5 6
|
Автор задачи: Дмитрий Иванков
Источник задачи: XIII чемпионат Урала по спортивному программированию, 4 апреля 2009 г.