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

Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014

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

E. Палиндромы и сверхспособности 2

Ограничение времени: 0.5 секунды
Ограничение памяти: 100 МБ
Дима дописывает к слову по одной букве s1, …, sn и после каждой буквы просит Мишу сказать, на сколько увеличилось число различных непустых подстрок-палиндромов после приписывания. Две подстроки считаются различными, если они различаются как строки. Какие n чисел назовёт Миша, если он никогда не ошибается?

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

На вход подаётся строка s1sn из строчных латинских букв ‘a’ и ‘b’ (1 ≤ n ≤ 5 000 000).

Результат

Выведите n чисел подряд без пробелов. При этом i-е число должно равняться количеству различных подстрок-палиндромов префикса s1si за вычетом этой же величины для s1si−1. Первое число должно равняться единице.

Пример

исходные данныерезультат
abbbba
111111

Замечания

Мы гарантируем, что жюри располагает решением на языке С++, укладывающимся в ограничение по времени хотя бы в два раза. Мы не гарантируем, что существует решение этой задачи на других языках (в том числе на Java).
Автор задачи: Михаил Рубинчик (Подготовка — Кирилл Бороздин)
Источник задачи: Ural FU Dandelion contest. Petrozavodsk training camp. Summer 2014
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2040. Палиндромы и сверхспособности 2