Generate all unique substrings for given string

Question

Given a string s, what is the fastest method to generate a set of all its unique substrings?

Example: for str = "aba" we would get substrs={"a", "b", "ab", "ba", "aba"}.

The naive algorithm would be to traverse the entire string generating substrings in length 1..n in each iteration, yielding an O(n^2) upper bound.

Is a better bound possible?

(this is technically homework, so pointers-only are welcome as well)

Answer 1

For big oh ... Best you could do would be O(n^2)

No need to reinvent the wheel, its not based on a strings, but on a sets, so you will have to take the concepts and apply them to your own situation.

Algorithms

Really Good White Paper from MS

In depth PowerPoint

Blog on string perms

Answer 2

There is no way to do this faster than O(n²) because there are a total of O(n²) substrings in a string, so if you have to generate them all, their number will be n(n + 1) / 2 in the worst case, hence the upper lower bound of O(n²) Ω(n²).

Answer 3

well, since there is potentially n*(n+1)/2 different substrings (+1 for the empty substring), I doubt you can be better than O(n*2) (worst case). the easiest thing is to generate them and use some nice O(1) lookup table (such as a hashmap) for excluding duplicates right when you find them.

greetz
back2dos

Answer 4

As other posters have said, there are potentially O(n^2) substrings for a given string, so printing them out cannot be done faster than that. However there exists an efficient representation of the set that can be constructed in linear time: the suffix tree.