eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Блоки строки

Блоки строки

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

Входные данные

Единственная строка S (|S| ≤ 10^6).

Выходные данные

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Пример

Входные данные #1
abaabaab
Выходные данные #1
0 0 1 5 0 1 2 0