Search code examples
c#c++algorithmsubstringsuffix-tree

unique substrings using suffix tree

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)?

Solution

  • 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.