Z-функция


Отправить решение Решать в редакторе

Сложность: 30%
Очки: 100 (частичный балл)
Ограничение по времени: 1.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Z-функция

Для каждой позиции i слова найдите длину наибольшего общего начала слова и его суффикса, который начинается в позиции i. Для i = 1 ответом считается длина всего слова.

Вход

Одна строка из строчных латинских букв, длина от 1 до 200000.

Выход

n чисел через пробел.

Пример 1

Вход

aaabaab

Выход

7 2 1 0 2 1 0

Пример 2

Вход

abc

Выход

3 0 0

Комментарии

Еще нет ни одного комментария.