#include <unordered_map>
#include <iostream>
#include <vector>
using namespace std;

void cleanup(const char*s, const char*p, vector<char> &str, vector<char> &pat){
	while (*s) str.push_back(*(s++));
	while (*p) {
		if (*p != '*') pat.push_back(*(p++));
		else {
			if (!pat.size() || pat.back() != '*') pat.push_back(*(p++));
			else ++p;
		}
	}
}

bool helper(int state, int offset, int strptr, int patptr, \
			vector<char> &str, vector<char> &pat, \
			unordered_multimap<int, int> &failoffset) {
	// DP part
	auto range = failoffset.equal_range(state);
	for (auto it = range.first; it != range.second; it++)
		if (it->second == offset) return false;

	int thisoffset;
	for (thisoffset = 0; thisoffset <= str.size() - strptr; thisoffset++) {
		int tmpstrptr = strptr + thisoffset;
		int tmppatptr = patptr + 1;
		while (tmppatptr != pat.size() && tmpstrptr != str.size() && \
			pat[tmppatptr] != '*' && \
			(str[tmpstrptr] == pat[tmppatptr] || pat[tmppatptr] == '?')) {
			tmppatptr++; tmpstrptr++;
		}
		if (tmppatptr == pat.size() && tmpstrptr == str.size()) return true;
		else if (tmppatptr == pat.size()) {
			failoffset.insert(make_pair(state, offset + thisoffset));
		}
		else if (tmpstrptr == str.size()) {
			while (pat[tmppatptr] == '*' && tmppatptr < pat.size()) tmppatptr++;
			if (tmppatptr == pat.size()) return true;
			failoffset.insert(make_pair(state, offset + thisoffset));
		}
		else if (pat[tmppatptr] != '*' && pat[tmppatptr] != str[tmpstrptr]) {
			failoffset.insert(make_pair(state, offset + thisoffset));
		}
		else if (pat[tmppatptr] == '*') {
			if (helper(state + 1, offset + thisoffset, tmpstrptr, tmppatptr, str, pat, failoffset))
				return true;
			failoffset.insert(make_pair(state, offset + thisoffset));
		}
	}
	failoffset.insert(make_pair(state, offset + thisoffset));
	return false;
}

bool isMatch(const char*s, const char*p) {
	vector<char> str, pat;
	unordered_multimap<int, int> um;
	cleanup(s, p, str, pat);
	int i = 0;
	int j = 0;
	while (i < str.size() && j < pat.size()) {
		if (str[i] == pat[j] || pat[j] == '?') {
			i++; j++;
			continue;
		}
		if (pat[j] == '*') break;
		return false;
	}
	if (i == str.size()) {
		while (j < pat.size() && pat[j] == '*') j++;
		if (j == pat.size()) return true;
		return false;
	}
	if (j == pat.size()) return false;
	str.erase(str.begin(), str.begin() + i);
	pat.erase(pat.begin(), pat.begin() + j);

	return helper(0, 0, 0, 0, str, pat, um);
}

int main() {
	char str[] = "abcdefg";
	char pat[] = "ab*e*f*g*";
	//char str[] = "a";
	//char pat[] = "a*";

	cout << isMatch(str, pat);

	return 0;
}