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;
        for(int y=0; y<=x; y++)
  • \$\begingroup\$ 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 \$\endgroup\$
    – geekpp
    Commented Nov 16, 2012 at 0:40
  • \$\begingroup\$ That would be all substrings, no? For example, with "abc", it would be "a","ab","abc","b","bc","c". \$\endgroup\$ Commented Nov 16, 2012 at 2:03
  • \$\begingroup\$ How about saying this, findCombinations ? \$\endgroup\$
    – Kinjal
    Commented Nov 16, 2012 at 4:58
  • 2
    \$\begingroup\$ What about equal substrings in strings like "aaa"? Are you allowed to print "aa" twice? \$\endgroup\$
    – Frank
    Commented Nov 16, 2012 at 8:35
  • 1
    \$\begingroup\$ @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). \$\endgroup\$
    – Corbin
    Commented Nov 16, 2012 at 9:48

1 Answer 1


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)
        int x=0;
        while(*(s + x))
            for(int y = 0; y <= x; y++)
                std::cout << *(s + y);
            std::cout << "\n";

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.

  • \$\begingroup\$ 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? \$\endgroup\$
    – Corbin
    Commented Nov 16, 2012 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.