#include <stack>
#include <string>
#include <iostream>

using namespace std;


bool IsMatch(const char *s, const char *p) 
{
    //when original string is enmpty,
    //only empty pattern or pattern with only asterisks would match it
    if (*s == '\0')
    {
        while(*p != '\0' && *p == '*') ++p;
        return (*p == '\0')? true : false;
    }
    //else (*s != '\0')
    //when orginal string is not empty, but patern is empty,
    //would not match
    if (*p == '\0') return false;

    bool hasAsterisk = false;

    while((*p != '\0' && *p != '*') && *s != '\0') 
        if(*s == *p || *p == '?')
            ++s, ++p;
        //first character is not asterisk, and first normal string is
        //not in the original string, match failed
        else return false;
    
    
    //find each normal strings in original string
    while(*p != '\0')
    {
        if (*p == '*')
		{
			hasAsterisk = true;
			++p;
			continue;
		}
        
        //search current part of normal string
		const char * ss = s;
		const char * sp = p;
		while(*s != '\0' && (*p != '\0' && *p != '*')) 
			if(*s == *p || *p == '?')
				++s, ++p;
			else
				s = ++ss, p = sp;
		
        //if string is not exist, 
        //check if rest of pattern is  either empty or only contains asteisks
        if(*s == '\0')return IsMatch(s, p);
    }

    //original string is not empty, match last normal string with pattern
    //from tail, if not match, the pattern could not match *whole* string
    if (*s != '\0')
    {
        if (!hasAsterisk)return false;
        if (*(--p) == '*') return true;
        
        while(s[1] != '\0') ++s;

        while(*p != '*' && (*s == *p || *p == '?'))--s, --p;

        return (*p == '*')? true : false;
    }

    return true;
}


int main(int argc, char** argv)
{
     char s[] = "aaabaaabbababaabbabaababbbbbbaabababbbaabaaaabbbba\
 bbbbaaaaabaabbbbaaaabbabbaaabbabbbababbaaaabbabbab\
 bbbabaabbabbbabbbbabbbbbaabbbababaaaababbbbabababa\
 bababbabbbbaaaaababbaaababbabaababbbaaabbbbbababab";
     char p[] = "aa*abab*a*a**a*b****ba*ba*aa*****b****b**bbbba*b*b*a**b**b*aab***b*bb***baa*b***a***baa*****a*a*a*ab**a";

    cout << (IsMatch(s, p)? "Matched" : "Not Matched") << endl; //Not Matched
	
	 s[sizeof(s)-2] = 'a';
	 cout << (IsMatch(s, p)? "Matched" : "Not Matched") << endl; //Matched

    return 0;
}