Find all possible substring in fastest way

Question

For String A = "abcd" then answer should be

{a,ab,abc,abcd,b,bc,bcd,c,cd,d} 

To find all the substring I have used following method

for (int i = 0; i < A.length(); i++) {
    for (int j = i+1; j <= A.length(); j++) {
        System.out.println(A.substring(i,j));
    }
}

But according to my understanding the complexity goes to O(N^2). Can we make it faster? I referred previous question and there was link for suffix tree but it doesn't seem to solve my problem. The output which I get from suffix tree is

{
 1: abcd
 2: bcd
 3: cd
 4: d
} 

Can any one please help me out to find fastest way to do this? Something like in linear time?

Solution

You can't create O(N^2) strings in better than O(N^2) time. It is a mathematical impossibility. Even if creating a string took one instruction, that is still a O(N^2) computation.

Putting complexity aside, I don't think your code can be improved upon in any significant way.

---

Can we make it faster?

Probably not.

Optimizing this particular piece of code is a futile activity. Since you are writing the strings to standard output, the actual performance will be dominated by the overheads of writing the characters ... and whatever the OS does with the output.

Comments

[Ankit Roy]

You can't possibly make it faster than O(n^2) to even list the starting and ending points of each possible substring, since there are O(n^2) such substrings! If you want to print out each substring in full (as you are currently doing), then the time complexity goes up to O(n^3) since it takes time proportional to the overall string length to print each substring.

[Philip]

Also note that the empty string is a valid substring as well.

[harold]

You can only make it faster if you're going to run a query over the set of substrings that doesn't "touch" them all. Printing them touches all of them. If you wanted to ask, say, "what is the longest substring that appears at least twice" or "which substring of more than k characters occurs most frequently", then you can do so without enumerating all substrings (with a suffix tree).

[HojjatK]

the for (int j = i+1; j <= A.length(); j++) line should be changed to for (int j = i+1; j <= A.length() - i; j++)