Menu
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.
448
Is there a way to print all substrings of a string in O(N) time? No there isn't. It is mathematically impossible. There are O(N^2) substrings of a string of length N .
The time complexity to generate all substring is O(N^3) time and there are O(N^2) sub-strings for a string of length N.
The total number of substrings formed by string of length N is (N*(N+1))/2, initialise count as (N*(N+1))/2.
If the length of a string is N, then there can be N – K + 1 substring of length K. Generating these substrings will require O(N) complexity, and checking each substring requires O(K) complexity, hence making the overall complexity like O(N*K). Efficient approach: The idea is to use Window Sliding Technique.
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).
188
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
