Practice Problem Set 4 (half-length)
Find the suffix array for the word sassafras (Include the end-of-string character, as in the lecture slides. Just list the positions of each suffix in the array; do not include the precomputed LCP information for fast searching. You do not have to go through the steps of the linear-time construction algorithm.)
Find a string \(s\) of six symbols from the two-symbol alphabet \(\{0,1\}\) (plus a seventh end-of-string character $) such that the suffix tree of \(s\) has only ten nodes in it. (Hints: for the suffix tree to be this small, every non-leaf node must have exactly three children. And for a non-leaf node to have a child starting with the symbol $, the substring that it represents must be a suffix of \(s\).)