# Find All Substrings Interview Query in C++

The following is my code for printing all the substrings of an input string. For example, with "abc", it would be "a","ab","abc","b","bc","c". Could someone please review it for efficiency (and possibly suggest alternatives)?

void findAllSubstrings(const char *s){
int x=0;
while(*(s+x)){
for(int y=0; y<=x; y++)
cout<<*(s+y);
cout<<'\n';
x++;
}
if(*(s+1))
findAllSubstrings(s+1);
else
return;
}

• what do you mean buy finding all sub strings? your code seams to print all characters in a string whith "xxx" it seems to print x xx xxx x xx x Nov 16 '12 at 0:40
• That would be all substrings, no? For example, with "abc", it would be "a","ab","abc","b","bc","c". Nov 16 '12 at 2:03
• How about saying this, findCombinations ? Nov 16 '12 at 4:58
• What about equal substrings in strings like "aaa"? Are you allowed to print "aa" twice? Nov 16 '12 at 8:35
• @Kinjal Sets have n^2 subsets, so at the base of the problem, n^2 is unavoidable (not to say that this code couldn't be optimized though). Nov 16 '12 at 9:48

Your problem is in O(n²), at least. This seems not to be optimizable. If you want only distinct substrings, then you will have to use a table of already encountered strings, which will make your code slower.

However, you can switch the algorithm from recursive to iterative, which is usually slightly faster. It's a micro-optimization, so do not expect a x2 improvement in speed...

void findAllSubstrings2(const char *s)
{
while(*s)
{
int x=0;
while(*(s + x))
{
for(int y = 0; y <= x; y++)
std::cout << *(s + y);
std::cout << "\n";
x++;
}
s++;
}
}


I've done a profile test, on Codepad and Ideone (different versions of same compilers + different machines). The io operations are left for the profile test, because what matters here is the comparison between the 2 functions.

• When an auxiliary stack isn't required and TCO isn't possible, converting recursion to iteration tends to have a very significant performance improvement. Definitely not a 2x improvement, but I definitely wouldn't consider it a micro optimization. In the case of a 3 character string, the recursion only goes 3 levels deep. What if the string were 100 characters? Nov 16 '12 at 21:15