CS 261, Spring 2026

Practice Problem Set 4 Solutions

1. 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.)

   Solution: The suffixes and their starting positions are

   • 0 : sassafras$
   • 1 : assafras$
   • 2 : ssafras$
   • 3 : safras$
   • 4 : afras$
   • 5 : fras$
   • 6 : ras$
   • 7 : as$
   • 8 : s$
   • 9 : $

   In alphabetically sorted order, with $ before any letter, they are:

   • 9 : $
   • 4 : afras$
   • 7 : as$
   • 1 : assafras$
   • 5 : fras$
   • 6 : ras$, 8 : s$
   • 3 : safras$
   • 0 : sassafras$
   • 2 : ssafras$

   So the suffix array is [9,4,7,1,5,6,8,3,0,2].

2. 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\).)

   Solution: Either 000100$ or 111011$ works. The two resulting suffix trees are shown below.