Задачи
Палиндромы и сверхспособности
Палиндромы и сверхспособности
После того как Миша решил на Тимусе семь задач со словом "палиндром" в названии, он приобрёл необыкновенную способность. Теперь, прочитав слово, он может посчитать в уме количество уникальных непустых подстрок этого слова, являющихся палиндромами.
Дима хочет проверить, не ошибается ли Миша. Для этого он дописывает к слову по одной букве s1
, ..., sn
и после каждой буквы просит Мишу сказать, сколько различных непустых подстрок-палиндромов содержит слово в данный момент. Какие n чисел назовёт Миша, если он действительно никогда не ошибается?
Входные данные
Строка s1...sn
(1 ≤ n ≤ 105
) из строчных латинских букв.
Выходные данные
Выведите n чисел: i-ое число должно равняться количеству различных подстрок-палиндромов префикса s1...si
.
Входные данные #1
aba
Выходные данные #1
1 2 3