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

#define bool int
#define false 0
#define true  1

static int match_pattern1(char *pat, char *str)
{
	switch (*pat) {
	case '\0':
		return !*str;
	case '*':
		return  match_pattern1(pat+1, str) ||
		        (*str && match_pattern1(pat, str+1));
	case '?':
		return *str && match_pattern1(pat+1, str+1);
	default:
		return *pat == *str && match_pattern1(pat+1, str+1);
	}
}

static bool match_pattern2(const char *pattern, const char *string)
{
	const char *s;
	const char *p;
	bool star = false;

loop:
	for (s = string, p = pattern; *s; ++s, ++p) {
		switch (*p) {
		case '?':
			break;
		case '*':
			star = true;
			string = s;
			pattern = p;
			if (!*++pattern)
				return 1;
			goto loop;
		default:
			if (*s != *p)
				goto star_check;
			break;
		}
	}
	if (*p == '*')
		++p;
	return (!*p);

star_check:
	if (!star)
		return 0;
	string++;
	goto loop;
}

static bool match_pattern3(const char *pattern, const char *string)
{
	const char *s = string;
	const char *p = pattern;
	bool star = false;

	while (*s) {
		switch (*p) {
		case '?':
			s++;
			p++;
			break;
		case '*':
			star = true;
			string = s;
			if (!*++p)
				return true;
			pattern = p;
			break;
		default:
			if (*s == *p) {
				s++;
				p++;
			} else {
				if (!star)
					return false;
				string++;
				s = string;
				p = pattern;
			}
			break;
		}
	}

	if (*p == '*')
		++p;
	return !*p;
}



/* return 0 if all the result of three function is same, else return 1. */
static int test_match()
{
	char *Str[] = { "ZIP",
	                ".ZIP",
	                "ZIP.",
	                "afdZfdaZIP"
	                "adfsafZfdsadfIfdafdsPfdasdf",
	                "accbddcrrfddhuulggnffphhqggyyyrnnvhgflllmmnnnnkpi.iuuuiyt",
	                "A.bkdfadfasfa.faskfa.sfaf?kl.A.ZIP",
	                "Asdhgerlthwegjsdklgjsdgjsdkgjsdgjsdg.ZIP",
	                "AAgsdjtweoruterjtertweiutwejtwejtwetwoejtwejtrwleAA.ZIP",
	                "Agjsdgjdsjgsdkjgsdjgsjd?gjsd?gjsd?gj?sdgj.A.ZIdgjsdkjglsdjgPPO",
	                "fasdfe323rerteter55rtrewtrwwe"
	              };
	char *Patt[] = { "?ZIP", "*ZIP", "ZIP.", "*ZIP", "*?ZIP", "?*?ZIP", "*?*?ZIP", "*Z*I*P*",
	                 "*?*?*ZIP", "a*?*?*ZIP", "*ZI?", "*ZI?", "*ZI*", "*ZI*",
	                 "a*?*?", "?*?*","ZIP", "ZIP", "AAZIP", "AZIP", "AAAAZIP", "AAZIPPO"
	               };
	int i = 0, j = 0, ret = 0;

	for (i = 0 ; i < sizeof(Patt)/sizeof(Patt[0]); i++) {
		for (j = 0; j < sizeof(Str)/sizeof(Str[0]); j++) {
			char *pat = Patt[i];
			char *str = Str[j];
			bool match1 = match_pattern1(pat, str);
			bool match2 = match_pattern2(pat, str);
			bool match3 = match_pattern3(pat, str);

			printf("\"%s\" =?= \"%s\"\n", pat, str);
			if (match1 == match2 && match2 == match3)
				printf("All three result is same: %d\n", match1);
			else {
				printf("****\n"
				       "****Someone is wrong: match1=%d match2=%d match3=%d\n"
				       "****\n",
				       match1, match2, match3);
				ret = 1;
			}
			printf("\n");
		}
		printf("\n");
	}
	return ret;
}

int main()
{
	return test_match();
}