1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm assuming you'd also like this to be shortened? It's considerably longer than the first version. \$\endgroup\$ – Jamal Sep 3 '13 at 12:24
  • \$\begingroup\$ Yes. This is still in the early stages. It passes the tests but as microtherion mentioned in his response I already have a bug. \$\endgroup\$ – AntonioCS Sep 3 '13 at 19:29
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ In the recursion example you give, to which do I add the +1? To the value or the wcard? \$\endgroup\$ – AntonioCS Sep 3 '13 at 19:38
  • 1
    \$\begingroup\$ You need both. For the greedy matcher, you first recurse with (value+1, wcard), i.e. you try eating the next character. If that fails, you recurse (or, since this is a tail recursion, iterate) with (value, wcard+1), i.e., match the rest of value without having the wildcard match any more characters. \$\endgroup\$ – microtherion Sep 3 '13 at 22:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.