# 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 Commented Nov 16, 2012 at 0:40
• That would be all substrings, no? For example, with "abc", it would be "a","ab","abc","b","bc","c". Commented Nov 16, 2012 at 2:03
• How about saying this, findCombinations ? Commented Nov 16, 2012 at 4:58
• What about equal substrings in strings like "aaa"? Are you allowed to print "aa" twice? Commented Nov 16, 2012 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). Commented Nov 16, 2012 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? Commented Nov 16, 2012 at 21:15