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?
Look up generalized suffix trees using Ukkonen's Algorithm. It's a very advanced piece of learning material, but you end up with a data structure that has all substrings using O(n) time.
