22137_CompressedSuffixArray

A new technology about suffix array called compressed suffix array is being researched. Let SA be the suffix array for string T. In the base case, we denote SA by SA₀, and let n₀ = n be the number of its entries. For simplicity in exposition, we assume that n is a power of 2. In the inductive phase k, we start with suffix array SA_k, which is available by induction. It has n_k = n/(2^k) entries and stores a permutation of {1, 2, ..., n_k }. (Intuitively, this permutation is that resulting from sorting the suffixes of T whose suffix pointers are multiple of 2^k.)

We run two main steps to transform SA_k into an equivalent but more succinct representation:

Step 1. We define a function Ψ_k where Ψ_k(i) = j if and only if SA_k[i] is odd and SA_k[j] = SA_k[i] + 1. In summary, for 1 ≤ i ≤ n_k , we have

Step 2. Pack together the even values from SA_k and divide each of them by 2. The resulting values form a permutation of { 1, 2, ... , n_k+1}, where n_k+1 = n_k/ 2 = n / 2^k+1 . Store them into a new suffix array SA_k+1 of n_k+1 entries, and remove the old suffix array SA_k.

The following example illustrates the effect of a single application of Steps 1-2.

SA₀ :

15 16 31 13 17 19 28 10 7 4 1 21 24 32 14 30 12 18 27 9 6 3 20 23 29 11 26 8 5 2 22 25

Ψ₀:

2 2 14 15 18 23 7 8 28 10 30 31 13 14 15 16 17 18 7 8 21 10 23 13 16 17 27 28 21 30 31 27

SA₁ :

8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11

Ψ_k can be stored in a particular way in O(n) bits, and SA_k+1 occupy half space of SA_k, So we can compress the suffix array by repeat steps 1-2. Now, the question is, if we have known SA_k+1 and how can we get the SA_k ?

You will be given a number of cases in the input. Each case starts with a line containing n. The first line contains a positive integer n, which is a power of 2, ( 2 ≤ n ≤ 2¹⁴ )

Followed by 2 lines.

The first line contains n integers represent for Ψ_k.

The second line contains k integers ( k = n / 2 ) represent for SA_k+1.

The input terminates with EOF.

For each input data set output one line, contains the numbers of SA_k (each number are separated by a space).

32
2 2 14 15 18 23 7 8 28 10 30 31 13 14 15 16 17 18 7 8 21 10 23 13 16 17 27 28 21 30 31 27
8 14 5 2 12 16 7 15 6 9 3 10 13 4 1 11

15 16 31 13 17 19 28 10 7 4 1 21 24 32 14 30 12 18 27 9 6 3 20 23 29 11 26 8 5 2 22 25