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?

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. — j_random_hacker, Mar 31 '13 at 05:28
Also note that the empty string is a valid substring as well. — Philip, Mar 31 '13 at 06:43
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). — harold, Mar 31 '13 at 11:09
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++)``` — HojjatK, Jun 09 '19 at 15:12
@HojjatK - The code in the question is correct. The 2nd argument to `substring` is an *exclusive* index, and therefore `j` *does* have to go up to `A.length()` ... inclusive. See the [javadoc](https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#substring(int,int)). — Stephen C, Dec 26 '22 at 03:08

Stephen C · Accepted Answer · 2020-12-27T07:23:47.903

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.

Find all possible substring in fastest way

1 Answers1

Linked