Can I generate all substrings in complexity < O(n^2)

Question

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.

Answer 1

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