Wildcard Matching Recursive Algorithm C++

Question

I have been writing a recursive wildcard matching algorithm in c++. But I'm having trouble completing it. Here look at what I write so far.

? matches any character, * matches any string

bool WildCardMatch(char *str, char *match){
 while (*match){
    if (*match =='?'){
        if (!*str){
            return false;
        }
        str++; 
        match++;
    }
    else if (*match == '*'){
        if (WildcardMatch(str, match + 1)){
            return true;
        }
        return false;
    }
 }
return !*str && !*match;
}

What's wrong with my algorithm? How should I fix it? Or can anyone suggest me a better solution for recursive wildcard matching algorithm?

What are the symptoms?

Galik
– Galik

2015-08-12 10:26:48 +00:00
Commented Aug 12, 2015 at 10:26 — Galik
– Galik, Commented Aug 12, 2015 at 10:26

Deadlock · Accepted Answer · 2015-08-12 10:20:19Z

2

Here look at this recursive wildcard matching algorithm. It will solve your troubles.

bool WildcardMatch(const TCHAR *pszString, const TCHAR *pszMatch){
while (*pszMatch)
{
    if (*pszMatch == _T('?'))
    {
        if (!*pszString)
            return false;

        ++pszString;
        ++pszMatch;
    }
    else if (*pszMatch == _T('*'))
    {
        if (WildcardMatch(pszString, pszMatch + 1))
            return true;

        if (*pszString && WildcardMatch(pszString + 1, pszMatch))
            return true;

        return false;
    }
    else
    {
        if (::CharUpper(MAKEINTRESOURCE(MAKELONG(*pszString++, 0))) != ::CharUpper(MAKEINTRESOURCE(MAKELONG(*pszMatch++, 0))))
            return false;
    }
}

return !*pszString && !*pszMatch;
}

answered Aug 12, 2015 at 10:20

Deadlock

4,5792 gold badges24 silver badges25 bronze badges

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

3 Comments

user1846749 Over a year ago

whats the time complexity?

Mingye Wang Over a year ago

@user1846749 For strings without *, linear. For strings with *, exponential with regard to the number of asterisks. See the discussion for the "ABORT" modification from 1993 in en.wikipedia.org/wiki/….

Mingye Wang Over a year ago

@user1846749 Alright, I've done porting the ABORT thing to this sample. See repl.it/repls/ScarceMinorTechnician.

Collectives™ on Stack Overflow

Wildcard Matching Recursive Algorithm C++

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related