Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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;
}
share|improve this question
    
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 –  geekpp 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". –  John Roberts Nov 16 '12 at 2:03
    
How about saying this, findCombinations ? –  Kinjal Nov 16 '12 at 4:58
1  
What about equal substrings in strings like "aaa"? Are you allowed to print "aa" twice? –  Frank Nov 16 '12 at 8:35
1  
@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). –  Corbin Nov 16 '12 at 9:48
show 5 more comments

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
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? –  Corbin Nov 16 '12 at 21:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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