Задачи
Блоки строки
Блоки строки
Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.
Вычислить длины блоков строки S для всех позиций.
Входные данные
Единственная строка S (|S| ≤ 10^6
).
Выходные данные
В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.
Пример
Входные данные #1
abaabaab
Выходные данные #1
0 0 1 5 0 1 2 0