Wildcard search in C version 2

Question

A few days ago, I posted my version of a wildcard search algorithm, which you can see here: Wildcard search in C

Today I'm showing version 2. I didn't want to make it in the same post because the code is quite different.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MULTICHAR '*'
#define ONECHAR '?'
#define null NULL

bool wildcard(const char *value, char *wcard) {

  int vsize = (int)strlen(value);
  int wsize = (int)strlen(wcard);
  bool match = false;

  if (vsize == 0 && wsize == 0) {
  match = true;
  }

  else {
  int v = 0;
  int w = 0;
  int lookAhead = 0;
  bool searchMode = false;
  char search = '\0';


  while (true) {
      if (wcard[w] == MULTICHAR) {
      //starts with * and the value matches the wcard
      if (w == 0 && strcmp(wcard+1,value) == 0) {
          match = true;
          break;
      }
      //the * is the last character in the pattern
      if (!wcard[w+1]) {
          match = true;
          break;
      }
      else {
          //search for the next char in the pattern that is not a ?
          while (wcard[++w] == ONECHAR) {
          lookAhead++;
          }

          //if the next char in the pattern is another * we go to the start (in case we have a pattern like **a, stupid I know, but it might happen)
          if (wcard[w] == MULTICHAR) {
          continue;
          }

          search = wcard[w];
          searchMode = true;
      }
      }

      else {
      if (!value[v] && !wcard[w]) {
          if (searchMode) {
          match = false;
          }
          break;
      }
      if (searchMode) {
          char currentValue = value[v+lookAhead];
          if (currentValue == search) {
          match = true;

          searchMode = false;
          search = '\0';
          lookAhead = 0;
          w++;
          }

          else if (currentValue == '\0') {
          match = false;
          break;
          }

          v++;
          continue;
      }
      else if ((wcard[w] == ONECHAR && value[v] == '\0') || (wcard[w] != value[v] && wcard[w] != ONECHAR)) {
          match = false;
          break;
      }
      else {
          match = true;
      }

      w++;
      v++;
      }
  }
  }

  return match;
}

I think there is still room for improvements, so any advice, tips or critiques are all welcome.

You can find the tests I ran here.

The project can be viewed here.

To compile, just do make wildcard.

Answer 1

I’m afraid your approach to matching multiple characters looks fundamentally misguided to me. Consider cases like:

abcbcd    ab*cd

One approach that works is a recursive matcher, i.e. when encountering *, try wildcard(value+1, wcard) and if that fails, wildcard(value, wcard+1). This will give you the standard semantics of an * matching as much as possible. For a minimal match, reverse the order of the two recursive calls. This is very easy to implement (much easier than your approach, in fact), but tends to need a lot of stack space for large strings.

The alternative is to build an explicit backtracking stack, which is considerably harder to get right, but uses less memory, and usually uses it on the heap rather than the stack.