A very simple recursive algorithm works for simple pattern matching:
int match_r(const char * pattern, const char * s)
{
switch (*pattern) {
case '\0': return !*s;
case '*': return match_r(pattern+1, s) || *s && match_r(pattern, s+1);
case '?': return *s && match_r(pattern+1, s+1);
default : return (*pattern == *s) && match_r(pattern+1, s+1);
}
}
A little bit more complex algorithm which can handle set of characters:
/* Scans a set of characters and returns 0 if the set mismatches at this */
/* position in the teststring and 1 if it is matching */
/* pattern is set to the closing ] and s is unmodified if mismatched */
/* and otherwise the char pointer is pointing to the next character */
int set(const char ** pattern, const char **s)
{
int fit = 0;
int neg = 0;
int beg = 1;
if ('!' == **pattern) {
neg = 1;
(*pattern)++;
}
while ((']' != **pattern) || (beg)) {
if (!fit) {
if (('-' == **pattern)
&& ((*(*pattern - 1)) < (*(*pattern + 1)))
&& (']' != *(*pattern + 1))
&& (!beg)) {
if (((**s) >= (*(*pattern - 1)))
&& ((**s) <= (*(*pattern + 1)))) {
fit = 1;
(*pattern)++;
}
} else if ((**pattern) == (**s)) {
fit = 1;
}
}
(*pattern)++;
beg = 0;
}
if (neg) fit = 1 - fit; /* change from zero to one and vice versa */
if (fit) (*s)++;
return (fit);
}
/* scans an asterisk */
int asterisk(const char ** pattern, const char ** s)
{
int fit = 1;
(*pattern)++; /* erase the leading asterisk */
while (**s && (('?' == **pattern) || ('*' == **pattern))) {
if ('?' == **pattern) (*s)++;
(*pattern)++;
}
/* Now it could be that s is empty and pattern contains */
/* aterisks. Then we delete them to get a proper state */
while ('*' == (**pattern)) (*pattern)++;
if (('\0' == (**s)) && ('\0' != (**pattern))) return (fit = 0);
if (('\0' == (**s)) && ('\0' == (**pattern))) {
return (fit = 1);
} else {
/* Neither s nor pattern are empty! */
/* the first character of pattern isn't in [*?] */
if (0 == match(*pattern, (*s))) {
do {
(*s)++;
/* skip as much characters as possible in the teststring */
/* stop if a character match occurs */
while (((**pattern) != (**s)) && ('[' != (**pattern)) && ('\0' != (**s))) (*s)++;
}
while ((('\0' != **s)) ? (0 == match(*pattern, (*s))) : (0 != (fit = 0)));
}
if (('\0' == **s) && ('\0' == **pattern)) fit = 1;
return (fit);
}
}
int match(const char * pattern, const char * s)
{
int fit = 1;
for (; *pattern && fit && *s; pattern++) {
switch (*pattern) {
case '[':
pattern++; /* leave out the opening square bracket */
fit = set(&pattern, &s);
/* we don't need to decrement the pattern as in case */
/* of asterisk because the closing ] is still there */
break;
case '?':
s++;
break;
case '*':
fit = asterisk(&pattern, &s);
/* the asterisk was skipped by asterisk() but the loop will */
/* increment by itself. So we have to decrement */
pattern--;
break;
default:
fit = (int) (*pattern == *s);
s++;
break;
}
}
while ((*pattern == '*') && fit) pattern++; /* here s is empty otherwise you cannot leave the previous loop */
return (int) (fit && ('\0' == *s) && ('\0' == *pattern));
}