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

Лучше поздно, чем никогда

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

J. Динамическая сложность строки

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Подстрока — это несколько подряд идущих символов в строке. Префикс строки — это подстрока, включающая первый символ строки. Суффикс строки — это подстрока, включающая последний символ строки.
Рассмотрим строку «квалификация». Строки «валик» или «акация» не являются её подстроками, т.к. буквы этих строк не идут в ней подряд. «валиф» и «каци» являются подстроками, при этом они обе не являются ни префиксом, ни суффиксом. «квал» является префиксом, а «кация» суффиксом строки. Сама строка «квалификация» является собственным суффиксом и префиксом.
В данной задаче мы считаем, что номера символов в строке индексируются с нуля.
Периодом строки S назовём минимальное положительное целое число T, для которого для любого 0 ≤ i < |S| верно, что S[i] = S[i mod T], где i mod T — остаток от деления i на T.
Грань строки — это её непустой префикс, который не является всей строкой и при этом равен её суффиксу. Сложностью строки назовём число различных периодов её граней. Динамической сложностью строки назовём сумму сложностей всех её префиксов.
Для заданной бинарной строки S и для каждого целого i от 1 до 25 требуется найти бинарные строки длины |S| + i, в которых строка S является префиксом, а их динамическая сложность будет наибольшей.

Исходные данные

В единственной строке находится бинарная строка S, 0 ≤ |S| ≤ 105, состоящая только из символов {X, .}.

Результат

Для каждого i от 1 до 25 требуется вывести максимальную динамическую сложность строки S + T, где |T| = i.

Пример

исходные данныерезультат
X.X
2
4
5
7
9
12
14
16
19
21
23
26
30
32
35
38
41
45
47
50
54
58
62
67
70
Автор задачи: Алексей Котельников, идея — Михаил Рубинчик, отдельная благодарность Владиславу Исенбаеву
Источник задачи: Контест "Лучше поздно, чем никогда"
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2137. Динамическая сложность строки