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.

I have been going through algorithms and data structures and recently came across string matching algorithms. I have not yet wrapped my head around the significance KMP algorithm so I came up with the function below. Is it really efficient or is there a better approach?

bool simplePatternMatch(const std::string &text, const std::string &pattern){
    //return true if pattern occurs otherwise false
    auto pat_it = pattern.begin();
    std::string::const_iterator it = text.begin();
    for(; it != text.end(); it++){
        if(*it == *pat_it){
            auto internal_it = it + 1;
            pat_it++;
            for(; internal_it != text.end();internal_it++){
                if( *internal_it == *pat_it)
                    pat_it++;
                else{
                    //a partial match occured so begin again to look for a match
                    pat_it = pattern.begin();
                    break;
                }
                if(pat_it == pattern.end())
                    return true;

            }

        }
    }
    //if we reach here there was no match
    return false;
}
share|improve this question
1  
Will fail for simplePatternMatch("CCAT", "CAT") –  Loki Astari Jun 23 at 20:43
    
I have fixed the bug in the function but I already have a feeling it is inefficient.Well atleast I see why we need the KMP algorithm:) –  michaelmwangi Jun 24 at 4:32
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.