String matching algorithm

Question

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;
}

Answer 1

Code Style

Whitespace and Braces

Be consistent in your usage of whitespace and braces. for and if statments should have a space between the keyword, parentheses, and opening brace (if using K&R style braces). Also, don't omit braces in an if, then include them in the else. For example:

if( *internal_it == *pat_it)
    pat_it++;
else{ // ...

Becomes:

if(*internal_it == *pat_it) {
    pat_it++;
} else { // ...

Reduce Variable Scope

it and internal_it are both declared outside their respective for statement, but are not referenced outside of it. Declaring them inside the for statement limits their scope to within the for loop, reducing opportunities for them to be misused. You can also use auto for type deduction, saving you the necessity of typing long iterator type names.

Reduce Nesting

Your code contains many nested if and for statements. This can make the code hard to read. If you have an if statement wrapping the entire loop body, you can reduce the level of nesting by inverting the condition and breaking early:

if(*it == *pat_it){
    // loop body
}

Becomes:

if (*it != *pat_it) {
    continue;
}
// loop body

Simplify, Simplify

Your inner for loop has almost exactly the same bounds as the outer loop. This can be simplified to a single loop over text and pattern each:

bool simplePatternMatch(const std::string &text, const std::string &pattern)
{
    // handle empty-string case
    if (pattern.empty() || text.empty())
    {
        return pattern.empty() && text.empty();
    }

    for(auto it = text.begin(); it != text.end(); it++) {
        auto pat_it = pattern.begin();
        while (pat_it != pattern.end() && *it == *pat_it) {
            ++it;
            ++pat_it;
        }
        if (pat_it == pattern.end()) {
            return true;
        }
    }

    //if we reach here there was no match
    return false;
}

You could change the while to a for and increment it and pat_it in the increment statement, but I find this more readable. Writing it this way also makes it explicit that there is a loop over each of your string arguments, which makes analyzing complexity much easier.

But wait! All that iterator comparison is complicated. Wouldn't it be nice if there was another way? Turns out, there is std::mismatch(), which is essentially what the inner loop does. Then the loop can be simplified:

for (auto it = text.begin(); it != text.end(); ++it) {
    const auto mismatches = std::mismatch(pattern.begin(), pattern.end(), it);
    if (mismatches.first == pattern.end()) {
        return true;
    }
}

Algorithm

Now that your function has been simplified a bit, it is easier to see that you have written a naive pattern match, which has complexity \$\mathcal{O}(mn)\$, where m is your pattern length, and n is the string length. You can improve upon this by implementing one of the well-known pattern-matching algorithms, like Boyer-Moore or Knuth-Morris-Pratt. I leave this as an exercise to you, both because it would make this answer too long, and it would be a good candidate for another question on Code Review.