Generate all unique substrings for given string
algorithm, language-agnostic
Solution
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.
Problem
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)