Find all possible substring in fastest way [duplic

问题:

This question already has answers here:

Generate all unique substrings for given string (14 answers)

Closed 2 years ago.

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?

回答1:

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