eolymp
bolt
Try our new interface for solving problems
Məsələlər

Преобразование строковых функций

Преобразование строковых функций

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Для строки S определим Z-функцию следующим образом: Z[i] = lcp(S, S[i..|S|]), где lcp(S_1, S_2) равно длине наибольшего общего префикса строк S_1 и S_2. Например, для S = abacabaaZ-функция равна [8, 0, 1, 0, 3, 0, 1, 1].

Для строки S определим ее префикс-функцию: pi[i] = max{k | 0 k < i, S[1..k] = S[i - k + 1..i]}. Например, для S = abacabaa ее префикс-функция имеет вид: [0, 0, 1, 0, 1, 2, 3, 1].

Для некоторой строки S была посчитана ее Z-функция, а строка S была утеряна. Ваша задача получить ее префикс-функцию по заданной Z-функции.

Giriş verilənləri

В первой строке входного файла содержится натуральное число N (1N200000), где N - длина S. Во второй строке записана Z-функция строки S.

Çıxış verilənləri

Выведите N чисел - искомую префикс-функцию.

Nümunə

Giriş verilənləri #1
8
8 0 1 0 3 0 1 1
Çıxış verilənləri #1
0 0 1 0 1 2 3 1