return all strings contains given string in suffix tree

Question

Here is my question:

Given a compressed suffix tree of string S and a substring T. I need to return all substrings of S that begins with the substring T sorted by lexicographic order.

My approach: I can traverse the suffix tree and find the edge / node which last letter of T is written on it. The subtree of this edge basically should be all the substrings of S beginning with the string T.

Am I right about this one? And How can I print all this subtree sorted?

Answer 1

Yes, you are right. You need to consume the symbols of $T$ and all occurrences of it shall be in the sub-tree below the position you stopped.

Since the edges are stored in lexicographical order, you can perform a Depth-first to print all the substrings of $S$ starting with $T$ in lexicographical order.

Using this example from Wikipediaenter image description here

and assuming $T = A,ドル we would arrive at an internal node. Doing a DFS, we would have: $A\$,ドル $ANA\$,ドル $ANANA\$$.