Transformation of String Functions: Inverse Problem

For a string $S$, the $Z$-function is defined as follows: Z[i] = lcp(S, S[i..|S|]), where lcp(S_1, S_2) represents the length of the longest common prefix between the strings S_1 and S_2. For instance, if S = abacabaa, the $Z$-function is [8, 0, 1, 0, 3, 0, 1, 1].

Additionally, for a string $S$, we define its prefix function as: pi[i] = \max\{k \mid 0 \le k < i, S[1..k] = S[i - k + 1..i]\}. For example, for S = abacabaa, the prefix function is [0, 0, 1, 0, 1, 2, 3, 1].

In this problem, the prefix function of a certain string $S$ is given, but the string itself is missing. Your task is to derive the $Z$-function from the provided prefix function.