Блоки строки

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

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

Технические условия

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

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

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

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

Информация о задаче

Лимит времени: 1 секунда
Лимит памяти: 64 MB
Баллы за пройденный тест: 1.6129
Сложность: 25% 18/24
Классификация: Алгоритмы на строках

Пример

Пример входных данных

abaabaab

Пример выходных данных

0 0 1 5 0 1 2 0

← Наибольшая грань подстроки

Список задач