我的做法如下：

将匹配格式串按照通配符划分为若干节插入Trie，并建立AC自动机和Fail树。具体来讲，我将两个*之间的部分视为一个大节，再以?划分小节。

判定文本串的首、尾是否强制要求匹配后（例如模式串aca?bb*vvd*dvwvw就要求首尾强制匹配），将中间剩余部分在AC自动机上跑，并在途径节点上记录对应的文本串的位置。完成后，对于每个模式串，遍历其末尾节点在Fail树上的子树，使用bitset记录它们在文本串上出现的位置。依次考虑每一个大节。若该大节中没有?通配符，则找到其在前面的大节考虑完后首次出现的位置（这样后面的字符可以有更多选择）；如果中间有?通配符，则容易发现，各个?通配符之间的串的出现位置应当能够构成一个排列，使得任两个小节的结尾字符的出现位置之差应该是第二个小节的长度加一。于是我们直接对bitset位移并做与运算（例如判定相邻两个小节$S_a, S_b$，则$S_a$的bitset向左位移$(len_{S_b}+1)$位并取与，就可以得到合法的$S_b$的位置，以此类推）。最后对于每个大节，我们取前面大节考虑完后的第一个合法排列的出现位置，以此类推。最终如果能在文本串的中间找到一个合法排列，就说明匹配成功；否则失败。

提交后始终在第四个点出错。本人已对自己能够设想的极端情况进行了对拍，无一输出错误答案。请各路大佬指正错误。变量名已调整得更加可读。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
char s[N], t[N];
int endsub[16], substartpos, sublen[16], x, n;
int slen, len, pos, subid, ed[16], segcnt, validseg;
int tr[N][26], cnt, fail[N];
int l, r;
queue <int> q;
bitset <N> appear[16], temp;
int head[N], e_cnt, vhead[N], v_cnt;
struct edge {
	int v, nxt;
} e[N];
struct rec {
	int pos, nxt;
} vis[N];
void add_e (int x, int y) {
	e[++e_cnt].nxt = head[x], head[x] = e_cnt, e[e_cnt].v = y;
}
void add_vis (int x, int pos) {
	vis[++v_cnt].nxt = vhead[x], vhead[x] = v_cnt, vis[v_cnt].pos = pos;
}

void process (int a, int b, int id) {
	x = 0;
	for (; a <= b; ++a) {
		if (!tr[x][s[a] - 'a']) tr[x][s[a] - 'a'] = ++cnt;
		x = tr[x][s[a] - 'a'];
	}
	ed[id] = x;
}
void build () {
	for (int i = 0; i < 26; ++i)
		if (tr[0][i]) {
			q.push (tr[0][i]);
			add_e (0, tr[0][i]);
		}
	while (q.size ()) {
		x = q.front (); q.pop();
		for (int i = 0; i < 26; ++i)
			if (tr[x][i]) {
				fail[tr[x][i]] = tr[fail[x]][i];
				add_e (tr[fail[x]][i], tr[x][i]);
				q.push (tr[x][i]);
			} else tr[x][i] = tr[fail[x]][i];
	}
}
void dfs (int x, int id) {
	for (int i = vhead[x]; i; i = vis[i].nxt)
		appear[id][vis[i].pos] = 1; // bitset赋值 
	for (int i = head[x]; i; i = e[i].nxt)
		dfs (e[i].v, id);
}
void query (int l, int r) {
	memset (vhead, 0, sizeof vhead);
	x = v_cnt = 0;
	for (; l <= r; ++l) {
		x = tr[x][t[l] - 'a'];
		add_vis (x, l); // 为了节省空间，使用链表存储对应位置 
	}
	for (int i = endsub[0] + 1; i <= endsub[segcnt - 1]; ++i) {  // 统一收集中间子串的结果
		appear[i].reset ();
		dfs (ed[i], i); // 遍历Fail树并收集第i个小节的出现位置 
	}
}

bool check () {
	l = 0, r = len - 1;
	for (; l < slen && s[l] != '*'; ++l) // 尝试匹配开头的强制匹配内容 
		if (s[l] != t[l] && s[l] != '?') return 0;
	for (int i = slen - 1; i >= 0 && r >= 0 && s[i] != '*'; --r, --i) // 结尾的强制匹配内容 
		if (s[i] != t[r] && s[i] != '?') return 0;
	if (l > r && validseg > 1) return 0; // 特判文本串长度已经不足的情况 
	query (l, r); // 对文本串剩下部分跑自动机 
	for (int seg = 2; seg < segcnt; ++seg) { // 从第二大段开始考虑每个大段 
		if (endsub[seg] - endsub[seg - 1] == 1) { // 该大段只有一个小节，说明没有?通配符 
			for (; l <= r; ++l)
				if (appear[endsub[seg]][l]) break; // 查询该段最早出现的位置 
			if (appear[endsub[seg]][l]) ++l;
			else return 0; // 未查询到，匹配失败 
		} else {
			temp = appear[endsub[seg - 1] + 1];
			for (int i = endsub[seg - 1] + 2; i <= endsub[seg]; ++i)
				temp = appear[i] & (temp << (1 + sublen[i])); 
			for (; l <= r; ++l)
				if (temp[l]) break;
			if (temp[l]) ++l;
			else return 0;
		}
	}
	return 1;
}

int main () {
	/* 洛谷题库 P3167 [CQOI2014]通配符匹配 CharlesWu */
	scanf ("%s", s); slen = strlen (s); // 匹配格式串的长度 
	for (int i = 0; i <= slen; ++i) {
		switch (s[i]) {
			case 0: // 在格式串的结尾也要划分一个大节，这样做会将形如 *aaaaa* 的格式串的首尾也划分上大节，方便后续处理 
			case '*':
				endsub[++segcnt] = subid + 1; // 记录每个大节中小节编号的最大值 
			case '?':
				process (substartpos, i - 1, ++subid); // 插入小节 
				sublen[subid] = i - endsub, substartpos = i + 1;
				break;
		}
	}
	validseg = segcnt - (endsub[segcnt] - endsub[segcnt - 1] == 1 && sublen[endsub[segcnt]] == 0) - (endsub[1] == 1 && sublen[1] == 0); // 包含至少一个长度非零小节的大段数量 
	build (); // 建AC自动机 
	scanf ("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf ("%s", t); len = strlen (t);
		printf ("%s\n", check () ? "YES" : "NO");
	}
	 
	return 0;
}