ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2009

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Шифровка 2

Ограничение времени: 3.0 секунды
Ограничение памяти: 64 МБ
Мюллер давно подозревал, что Штирлиц периодически отсылает шифровки в СССР. И вот, наконец, он почти поймал его за руку: роясь в бумагах Штирлица, он нашёл непонятный набор цифр, записанный на чистом листе. Сразу догадавшись, что это шифровка, он вызвал Штирлица на допрос. Тот же невозмутимо объяснил, что это всего лишь номер лотерейного билета, который он переписал на лист бумаги, чтобы не забыть. Штирлиц никогда не был так близок к провалу — ведь на листе были записаны координаты бункера Гитлера.
Для передачи этих данных в Центр Штирлиц использовал следующий алгоритм:
  • На вход подаётся строка s = s1s2sn.
  • Выбирается ключ k — целое положительное число, строго меньшее n.
  • Для каждого символа строки si выполняется следующая процедура:
    1. Рассматривается строка qi, состоящая из k подряд идущих символов строки s, начиная с i-го: qi = sisi + 1si + k − 1. Если до конца строки не набирается k символов, то оставшиеся символы берутся из начала строки: qi = sisns1si + k − 1 − n.
    2. Для строки 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 г.
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1706. Шифровка 2