B. Префикс-функция

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

Бордер строки — это её собственный префикс, одновременно являющийся её суффиксом. Собственный значит короче самой строки.

Префикс-функция $p_i$ — длина наибольшего бордера префикса $s[0..i]$ . Значение $p_0$ равно нулю.

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

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

ввод

abacaba

вывод

0 0 1 0 1 2 3

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

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