A. Z-функция

3000 мс · 256 МБ · всё или ничего

Для строки $s$ длины $n$ значение $z_i$ — длина наибольшего общего префикса строки $s$ и её суффикса, начинающегося в позиции $i$ . Значение $z_0$ считается равным $n$ .

Формат ввода

Одна строка из строчных латинских букв длиной не больше $10^6$ .

Формат вывода

Одна строка из $n$ чисел — значения Z-функции.

Примеры

ввод

abacaba

вывод

7 0 1 0 3 0 1

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.