String Wildcard Matching (* and ?)

Does not work with

pattern_match("zcdxzcdxcd", "*cdxcd")

char str[]=suddh"; char pat[]="su*ddh" Answer should be true but it return false

I was looking for something like this but didn't think much of this code.

After spending some time considering how to implement wildcard matching properly I came up with the following:

C++

// wildcard matching algorithm
// written 2013 by Mathias Karlsson <tmowhrekf@gmail.com>
// use freely.

bool wildcard(const char *str, const char *pattern);

bool wildcard(const char *s, const char *p)
{
	// ? matches one character
	// * matches zero or more characters
	while (*s) {
		if (!*p) return false;
		if (*p == '*') {
			while (*p == '*') p++;
			if (!*p) return true;
			while (*s) if (wildcard(s++, p)) return true;
			return false;
		}
		if (*s != *p && *p != '?') return false;
		p++;
		s++;
	}
	while (*p == '*') p++;
	return (!*p);
}

If you have examples where it would fail then please reply to this or send me a message.

Of course, if there are security concerns you should limit the string lengths and the call stack.

Hopefully this code will help someone.

modified 31-Mar-13 13:59pm.

Exactly my thoughts tmowhrekf. I think your code is perfect since I've reached the same conclusions.
Just one minor detail though, you should reverse the order of "(*p != '?' && *s != *p)", since "*p != '?'" will be true more often than "*s != *p". That way you'll only be checking one condition instead of two most of the time.

Regards.

You are right. I have modified the above example to help the compiler (which couldn't know this).

However, if you are really trying to optimize for speed there would be faster methods for most purposes (precompiling the pattern, recognizing common pattern formats, maybe using faster stacks instead of recursive calls, etc.) but the code here is visible and accurate as an algorithm.

modified 24-Mar-13 11:06am.

All I ever use is this kind of simple pattern matching and your code have worked like a char (at least so far hehe).

I have only changed a few things to make it unicode friendlier, added a switch instead of thoese nested ifs up there and that was it. Thanks.

Here is my modified version

bool pattern_match(LPCTSTR str, LPCTSTR pattern)
{
    enum State {
        Exact,      // exact match
        Any,        // ?
        AnyRepeat   // *
    };

    LPCTSTR s = str;
    LPCTSTR p = pattern;
    LPCTSTR q = 0;
    int state = 0;

    bool match = true;
    while (match && *p)
    {
        switch(*p)            
        {
            case __T('*'):
                state = AnyRepeat;
                q = p+1;
                break;
        
            case __T('?'):
                state = Any;
                break;
        
            default:
                state = Exact;
                break;
        }

        if(*s == 0)
            break;

        switch (state)
        {
            case Exact:
                match = *s == *p;
                s++;
                p++;
                break;

            case Any:
                match = true;
                s++;
                p++;
                break;

            case AnyRepeat:
                match = true;
                s++;
                if(*s == *q)
                    p++;
                break;
        }
    }

    if(state == AnyRepeat)
        return (*s == *q);
    else
    if(state == Any)
        return (*s == *p);
    else
        return match && (*s == *p);
}

Nice small and simple code.

However, the simple match abcbde with *bd* fails.

In the above case, the routine will find that the first "b" after the wildcard matches the source after the "a", but the following "d" in the patterh doesn't match the "c" from the source and returns false, although the sequence "bd" exists later in the string.

If one character fails in the "exact matching" routine after a wildcard, the routine should extend the wildcard and search the rest of the string and see whether the exact match comes later in the string.

I was able to address the bug by modifying the following section:

case AnyRepeat:
match = true;
s++;

if (*s == *q) p++;
break;

to
case AnyRepeat:
match = true;
s++;

if (*s == *q){
// make a recursive call so we don't match on just a single character
if (pattern_match(s,q) == true {
p++;
}
}
break;

Exactly what i was looking for - thank you.

Alex

You're welcome. I'm glad that this is useful for someone.
Smile | :)

You may read the article in http://www.codeguru.com/cpp/cpp/string/alts/article.php/c2807/ for more details.

Yuantu

but this article is not on codeproject, but on codeguru which is so bad website Wink | ;)

I agree. CodeGuru is a pathetic repost that is mostly advertising.
CodeProject is my primary source for *real* (and really useful) code.

String Wildcard Matching (* and ?)

Introduction

Using the Code

History

License

Comments and Discussions