CODEWITHSUNDEEP
c++stringpattern-matchingstring-matching
Aan
Aan

Reputation: 12890

String matching implementation

I wrote the below code to check whether a certin string exists in a text or no. The issue is that match() function always returns false even the pattern exists in the text.

int main(){

    char *text="hello my name is plapla";
    char *patt="my";

    cout<<match(patt,text);

    system("pause");
    return 0;
}

bool match(char* patt,char* text){

    int textLoc=0, pattLoc=0, textStart=0;
    while(textLoc <= (int) strlen(text) && pattLoc <= (int)strlen(patt)){
        if( *(patt+pattLoc) == *(text+textLoc) ){
            textLoc= textLoc+1;
            pattLoc= pattLoc+1;

        }

        else{
            textStart=textStart+1;
            textLoc=textStart;
            pattLoc=0;
        }

    }
    if(pattLoc > (int) strlen(patt))
        return true;
    else return false;
}

Upvotes: 1

Views: 3005

Answers (3)

yngccc
yngccc

Reputation: 5684

Try pattLoc < (int)strlen(patt) in your while loop. Loop will stop when pattLoc == 2, so you avoid comparing the '\0' of "my" with the ' ' of "hello my name is pala", which set pattloc to 0 and return false.

Or better, use string substr.

Upvotes: 3

Aan
Aan

Reputation: 12890

I have solved the problem:

while(textLoc <= (int) strlen(text) && pattLoc <= (int)strlen(patt))

should be:

while(textLoc < (int) strlen(text) && pattLoc < (int)strlen(patt))

and if(pattLoc > (int) strlen(patt)) to if(pattLoc >= (int) strlen(patt))

Upvotes: 0

James Kanze
James Kanze

Reputation: 153919

The obvious solution is:

bool
match( std::string const& pattern, std::string const& text )
{
    return std::search( text.begin(), text.end(), 
                        pattern.begin(), pattern.end() )
            != text.end();
}

This is idiomatic C++, and the way I would expect any C++ programmer to write it, at least in a professional environment.

If the goal is to learn how to write such a function, then of course, the above isn't much of a solution. The solution then should be mroe divide and conquer; there's much too much in match for you to put it in one function. I'd recommend something like:

bool
startsWith( std::string::const_iterator begin,
            std::string::const_iterator end,
            std::string const& pattern )
{
    return end - begin >= pattern.size()
        && std::equal( pattern.begin(), pattern.end(), begin );
}

bool
match( std::string const& pattern, std::string const& text )
{
    std::string::const_iterator current = text.begin();
    while ( current != text.end()
            && !startsWith( begin, text.end(), pattern ) ) {
        ++ current;
    }
    return current != text.end();
}

This can obviously be improved; for example, there's no point in continuing in the while loop when the length of the remaining text is less than the length of the pattern.

And if your professor insists on your using char const* (if he insists on char*, then he's totally incompetent, and should be fired), this can easily be rewritten to do so: just replace all calls to begin with the pointer, and all calls to end with pointer + strlen(pointer).

Upvotes: 1

Related Questions