Suffix structures

Questions 1 to 5 of 8

1. 1. The lesson's suffix array code sorts suffixes with prefix doubling. What are its time and memory costs?

   O(n) time, because one sort by first character finishes the job.O(n log n) time and O(n) memory, from about log n rounds of doubling with linear work in each round.O(n^2) memory, because every suffix is stored before the sort.O(n^2) time, because two suffixes are always compared letter by letter.
2. 2. In Kasai's method for the LCP array, why is the total work O(n)?

   The comparison loop runs once per position, with no inner loop.Each round of prefix doubling halves the number of suffixes that still need work.The value h rises by one per letter comparison and drops by at most one as i moves right, so the total is at most about 2n.The LCP of each neighbour pair is looked up in a sparse table.
3. 3. An AI defines lcp[r] as the LCP of sa[r] and sa[r+1], and answers queries with the minimum of lcp[l+1..r]. What is wrong?

   Nothing is wrong, because the two indexes are interchangeable.The definition is shifted. lcp[r] must be the LCP of sa[r-1] and sa[r], and with the shifted version the range minimum is wrong for some queries.lcp[0] must hold the length of the text.An LCP array cannot be used with a sparse table.
4. 4. The text is banana. Its suffix array is 5 3 1 0 4 2. What is the LCP of the suffixes at positions 3 (ana) and 1 (anana)?

   Type a number.

5. 5. Put these steps of one suffix automaton extend (adding a letter c) in order.

   Use the arrows to put the steps in order.

   1. 1.Walk suffix links from last, adding a transition by c to each state that has none↑↓
   2. 2.Set the links of q and cur to the clone, or to 0 when the walk found no state↑↓
   3. 3.Set last to cur↑↓
   4. 4.Create the new state cur with len equal to len(last) + 1↑↓
   5. 5.If the walk meets a state p whose transition by c leads to q with len(p) + 1 < len(q), clone q and redirect the transitions that point to q↑↓