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?


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\$$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.