String matching implementation

Question

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

Why are you not using std::string? Any particular reason or just love for c? — Alok Save
– Alok Save, Commented Jan 31, 2012 at 18:26
Instead of *(patt+pattLoc) you can use patt[pattLoc], but since you love parts of C, I think textLoc should rather be a char *. — ipc
– ipc, Commented Jan 31, 2012 at 18:27
@Adban Wait, so you actually like pointers and raw memory management? — Etienne de Martel
– Etienne de Martel, Commented Jan 31, 2012 at 18:30
You're really going to want to move the strlens outside of the loop, or hope your compiler is smart. — Mooing Duck
– Mooing Duck, Commented Jan 31, 2012 at 18:30

logancautrell · Accepted Answer · 2012-01-31 21:12:04Z

3

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.

edited Jan 31, 2012 at 21:12

logancautrell

8,7633 gold badges41 silver badges50 bronze badges

answered Jan 31, 2012 at 18:56

yngccc

5,7042 gold badges27 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

James Kanze Over a year ago

string::substr is likely to have even worse performance than his multiple calls to strlen (although it's far from sure). For better or for worse, the C++ library is designed around iterators.

James Kanze · Accepted Answer · 2012-01-31 19:02:00Z

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).

Aan · Accepted Answer · 2012-01-31 19:15:32Z

0

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))

answered Jan 31, 2012 at 19:15

Aan

13k36 gold badges94 silver badges151 bronze badges

Collectives™ on Stack Overflow

String matching implementation

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related