Can I generate all substrings in complexity < O(n^2)
java, substring, suffix-tree
Solution
There are `O(n^2)` different substrings, so no algorithm can enumerate them all with a complexity better than `O(n^2)`!
The problem of finding the lexicographically smallest substring is a totally different one, though. It's always the empty string, so that's an `O(1)` operation (and a very pointless one, too).
Problem
Currently I am using two nested `for` loop to generate all the substrings of a string. I heard about `Suffix Tree` but AFAIK `Suffix Tree` generates suffix not the substrings. Following is the code which currently i am using- ``` String s = "abacbccca"; int l = s.length(); for (short c = 0; c < l; c++) { for (short r = 0; r < l - c; r++){ Sting ss=s.substring(c, c + r + 1); if(!t.contains(ss)); t.add(ss); } } ``` I want a way which can generate all the substrings in less than `O(n^2)`. Although by seeing my code, anyone can suggest me that it's impossible, as i am adding every substring to a list. But my objective is not to store all the substrings, my objective is to find a string which is lexicographically ith smallest string.