unique substrings using suffix tree

Question

For a given string S of length n-

• Optimal algorithm for finding all unique substrings of S can't be less than O(n^2). So, the best algorithm will give us the complexity of O(n^2). As per what I have read, this can be implemented by creating suffix tree for S.

The suffix tree for S can be created in O(n) time. Now, my question is-

How can we use the suffix tree for S to get all the unique substrings of S in O(n^2)?

Answer 1

Try to read about suffix arrays: http://en.wikipedia.org/wiki/Suffix_array This method is faster than suffix tree for getting substrings in string.

Answer 2

It can be done optimally through tries. Add the strings to trie and traverse from root to node. Each root to node path will denote suffixes of a string. Take all the prefixes of these suffixes. These are the unique substrings.