We'll discuss this in class. For the assignment, don't worry about building a suffix tree quickly, just find a way to build it. Follow q into the suffix tree and find the node N at or below q. Note that k is both the number of leaves examined and the number of answers that must be reported. Once the suffix tree for S is built, many queries can be done.
Suffix trees have many other uses.
We'll talk about some more ways to use them in class.