CHAPTER 12
Advanced Data Structures and Implementation
12.3 Incorporate an additional field for each node that indicates the size of its subtree. These fields are easy to
12.6 If there are B black nodes on the path from the root to all leaves, it is easy to show by induction that there are
12.7 Color nonroot nodes red if their height is even and their parents height is odd, and black otherwise. Not all
12.8 The problem asks us to compute the suffix array, LCP array, and suffix tree for the two strings
C
BC
ABC
CABC
is by indicating the index of its first character. (9 – length of suffix)
Index
Suffix
6
ABC
3
ABCABC
0
ABCABCABC
1
BCABCABC
8
C
In the case of MISSISSIPPI, the possible suffixes are:
I
PI
PPI
And we need to alphabetize them to produce the suffix array. Beside each one we can identify which suffix it
Index
Suffix
10
I
7
IPPI
4
ISSIPPI
1
ISSISSIPPI
0
MISSISSIPPI
9
PI
8
PPI
6
SIPPI
3
SISSIPPI
5
SSIPPI
2
SSISSIPPI
Now for the LCP arrays. The first suffix does not have an LCP (longest common prefix). For each of the
5
CABC
2
CABCABC
We can complete the tables as follows. For ABCABCABC, we have:
Index
LCP
Prefix
6
–
ABC
7
0
BC
4
2
BCABC
8
0
C
5
1
CABC
2
4
CABCABC
For MISSISSIPPI, we have:
Index
LCP
10
–
7
1
4
1
1
4
0
0
9
0
8
1
6
0
3
2
5
1
2
3
Finally, we draw the suffix trees for each string.
3
3
ABCABC
0
6
ABCABCABC
12.9 (a) We see that for all i, rank[sa[i]] = i. Thus, rank and sa are inverses of each other. The sa array gives the
list of suffixes in alphabetical order. In other words, sa[4] tells you what the 5th suffix is in alphabetical
(b) Need to show that LCP[rank[i]] == h implies LCP[rank[i+1]] >= h–1.
The reason why we have the big IF statement: if (rank[i] > 0) is because we want to avoid computing
So, when we compare LCP[rank[i]] and LCP[rank[i+1]], there are two cases. First, if LCP[rank[i]] > 0, then
this means that the substring in s starting at i matches another substring in the word. When we advance from
(c) By definition, the LCP of a suffix is the number of initial characters that match the suffix that
immediately precedes it in the alphabetical listing of suffixes. For example, the [1] and [2] suffixes in the
(d) The algorithm consists of a loop that runs for N iterations. The only doubt that the algorithm might
execute in more than O(N) time is the fact that there is an inner while loop. However, the inner loop does not
12.13 See H. N. Gabow, J. L. Bentley, and R. E. Tarjan, “Scaling and Related Techniques for Computational
Geometry,” Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (1984), 135 –
12.23 A linked structure is unnecessary; we can store everything in an array. This is discussed in reference [12].
12.29 Consider the pairing heap with 1 as the root and children 2, 3, . . . N. A deleteMin removes 1, and the