#include <stdio.h>
 
unsigned matches(char const * const input, char const * const pattern) {
  if (! *pattern) {
    // An empty pattern matches only the empty
    // string, nothing else
    return (*input) ? 0 : 1;
  }
  if (*pattern == '*') {
    // a wildcard could be zero to any number
    // of characters. Sum the number of matches
    // for each possibility (excluding the empty
    // rest of input for now)
    char const * rest = input;
    unsigned count = 0;
    while (*rest) {
      count += matches(rest, pattern + 1);
      ++rest;
    }
    // Add matches for the empty rest of input
    count += matches(rest, pattern + 1);
    return count;
  }
  if (! *input) {
    // A non empty, non wildcard pattern cannot
    // match the empty string
    return 0;
  }
  if (*pattern == *input) {
    // non wildcard match, count the ways the rest of
    // the pattern matches the rest of the input.
    return matches(input + 1, pattern + 1);
  }
  else {
    // mismatch!
    return 0;
  }
}
 
int main() {
  char const * const inputs[] = {
    "a", "aa", "xxa", "abx", "", "x", "aabb",
    "absolutely awesome but ..."};
  char const * const patterns[] = {
    "", "a", "*a", "a*", "*a*",
    "ab*", "*ab*", "**a", "*a*b*"};
  size_t p, i;
  size_t const numPatterns =
    sizeof(patterns)/sizeof(patterns[0]);
  size_t const numInputs =
    sizeof(inputs)/sizeof(inputs[0]);
  for (i = 0; i < numInputs; ++i) {
    printf("%s:\n", inputs[i]);
    for (p = 0; p < numPatterns; ++p) {
      printf("%s matches %u times\n",
        patterns[p],
        matches(inputs[i], patterns[p]));
    }
  }
  return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+Cgp1bnNpZ25lZCBtYXRjaGVzKGNoYXIgY29uc3QgKiBjb25zdCBpbnB1dCwgY2hhciBjb25zdCAqIGNvbnN0IHBhdHRlcm4pIHsKICBpZiAoISAqcGF0dGVybikgewogICAgLy8gQW4gZW1wdHkgcGF0dGVybiBtYXRjaGVzIG9ubHkgdGhlIGVtcHR5CiAgICAvLyBzdHJpbmcsIG5vdGhpbmcgZWxzZQogICAgcmV0dXJuICgqaW5wdXQpID8gMCA6IDE7CiAgfQogIGlmICgqcGF0dGVybiA9PSAnKicpIHsKICAgIC8vIGEgd2lsZGNhcmQgY291bGQgYmUgemVybyB0byBhbnkgbnVtYmVyCiAgICAvLyBvZiBjaGFyYWN0ZXJzLiBTdW0gdGhlIG51bWJlciBvZiBtYXRjaGVzCiAgICAvLyBmb3IgZWFjaCBwb3NzaWJpbGl0eSAoZXhjbHVkaW5nIHRoZSBlbXB0eQogICAgLy8gcmVzdCBvZiBpbnB1dCBmb3Igbm93KQogICAgY2hhciBjb25zdCAqIHJlc3QgPSBpbnB1dDsKICAgIHVuc2lnbmVkIGNvdW50ID0gMDsKICAgIHdoaWxlICgqcmVzdCkgewogICAgICBjb3VudCArPSBtYXRjaGVzKHJlc3QsIHBhdHRlcm4gKyAxKTsKICAgICAgKytyZXN0OwogICAgfQogICAgLy8gQWRkIG1hdGNoZXMgZm9yIHRoZSBlbXB0eSByZXN0IG9mIGlucHV0CiAgICBjb3VudCArPSBtYXRjaGVzKHJlc3QsIHBhdHRlcm4gKyAxKTsKICAgIHJldHVybiBjb3VudDsKICB9CiAgaWYgKCEgKmlucHV0KSB7CiAgICAvLyBBIG5vbiBlbXB0eSwgbm9uIHdpbGRjYXJkIHBhdHRlcm4gY2Fubm90CiAgICAvLyBtYXRjaCB0aGUgZW1wdHkgc3RyaW5nCiAgICByZXR1cm4gMDsKICB9CiAgaWYgKCpwYXR0ZXJuID09ICppbnB1dCkgewogICAgLy8gbm9uIHdpbGRjYXJkIG1hdGNoLCBjb3VudCB0aGUgd2F5cyB0aGUgcmVzdCBvZgogICAgLy8gdGhlIHBhdHRlcm4gbWF0Y2hlcyB0aGUgcmVzdCBvZiB0aGUgaW5wdXQuCiAgICByZXR1cm4gbWF0Y2hlcyhpbnB1dCArIDEsIHBhdHRlcm4gKyAxKTsKICB9CiAgZWxzZSB7CiAgICAvLyBtaXNtYXRjaCEKICAgIHJldHVybiAwOwogIH0KfQoKaW50IG1haW4oKSB7CiAgY2hhciBjb25zdCAqIGNvbnN0IGlucHV0c1tdID0gewogICAgImEiLCAiYWEiLCAieHhhIiwgImFieCIsICIiLCAieCIsICJhYWJiIiwKICAgICJhYnNvbHV0ZWx5IGF3ZXNvbWUgYnV0IC4uLiJ9OwogIGNoYXIgY29uc3QgKiBjb25zdCBwYXR0ZXJuc1tdID0gewogICAgIiIsICJhIiwgIiphIiwgImEqIiwgIiphKiIsCiAgICAiYWIqIiwgIiphYioiLCAiKiphIiwgIiphKmIqIn07CiAgc2l6ZV90IHAsIGk7CiAgc2l6ZV90IGNvbnN0IG51bVBhdHRlcm5zID0KICAgIHNpemVvZihwYXR0ZXJucykvc2l6ZW9mKHBhdHRlcm5zWzBdKTsKICBzaXplX3QgY29uc3QgbnVtSW5wdXRzID0KICAgIHNpemVvZihpbnB1dHMpL3NpemVvZihpbnB1dHNbMF0pOwogIGZvciAoaSA9IDA7IGkgPCBudW1JbnB1dHM7ICsraSkgewogICAgcHJpbnRmKCIlczpcbiIsIGlucHV0c1tpXSk7CiAgICBmb3IgKHAgPSAwOyBwIDwgbnVtUGF0dGVybnM7ICsrcCkgewogICAgICBwcmludGYoIiVzIG1hdGNoZXMgJXUgdGltZXNcbiIsCiAgICAgICAgcGF0dGVybnNbcF0sCiAgICAgICAgbWF0Y2hlcyhpbnB1dHNbaV0sIHBhdHRlcm5zW3BdKSk7CiAgICB9CiAgfQogIHJldHVybiAwOwp9