对每个串分别考虑

发现如果模式串的最左端不是"*" 则文本串与模式串必须有相同的前缀 右端同理

我们先将文本串与模式串的相同前缀后缀去掉

这时候模式串被若干个"*"分成了若干段

只需要这若干段能按顺序匹配到文本串即可

实现：

按顺序考虑每一段模式串 贪心地在文本串上找第一个匹配的位置

为什么选择最靠前的？ 假设当前不是最靠前的匹配 那么一定有一个更靠前的匹配 使其既能匹配，又能减少（不增多）对后面的阻碍 显然更优

我采用hash 把"?"的地方扣掉 注意到"?"的个数不超过10 所以可过

总复杂度$O(n*len*k)$ k是"?"的个数

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9;
const int mul=911,mod=1e15+37;
string s,t;
int len,n,ls;
int a[1010000],b[1010000];
int now[1010000],tot;
int fm[1010000];
int sts=0;//"*"的个数 
int wh[101],wtt;
int ok(int x,int y){
	//判断两个字符是否可以匹配 
	if(x==0||y==0||x==y) return 1;
	return 0;
}
int trry(int fr,int to){
	//找第一个匹配 
	if(tot==0) return fr; 
	if(to-fr+1<tot) return inf;
	wtt=0;
	int H=0,Hp=0;
	for(int i=1;i<=tot;i++){
		if(now[i]==0) wh[++wtt]=i;
		H=(H*mul+now[i])%mod;
	}
	for(int i=fr;i<=fr+tot-1;i++){
		Hp=Hp*mul%mod;
		if(now[i-fr+1]){
			Hp=(Hp+b[i])%mod;
		} 
	}
	for(int beg=fr,ed=fr+tot-1;ed<=to;){
		if(Hp==H) return ed+1;
		for(int j=1;j<=wtt;j++){
			Hp=Hp+b[beg+wh[j]-1]*fm[tot-wh[j]];
			Hp%=mod;
		}
		Hp=((Hp-b[beg]*fm[tot-1])%mod+mod)%mod*mul%mod;
		beg++;
		ed++;
		Hp+=b[ed]; 
		for(int j=1;j<=wtt;j++){
			Hp=Hp-b[beg+wh[j]-1]*fm[tot-wh[j]];
			Hp%=mod;
		}Hp=(Hp%mod+mod)%mod;
	}
	return inf;
}
int resolve(int lens,int lenn,int frs,int frn){
	//判断分段后是否可行 
	int p=frn;tot=0;
	for(int i=frs;i<=lens;i++){
		if(a[i]==-1){
			p=trry(p,lenn);
			tot=0;
		} 
		else{
			now[++tot]=a[i];
		}
		if(p>lenn+1) return 0;
	}
	return 1;
}
int solve(){
	if(ls-sts>len) return 0; 
	if(sts==0){
		//特判 
		if(len!=ls) return 0;
		for(int i=1;i<=len;i++){
			if(ok(a[i],b[i])==0) return 0;
		}return 1;
	}else{
		//去掉共同前缀后缀 
		int i=ls,j=len;
		for(;a[i]!=-1;i--,j--){
			if(a[i]==-1) break;
			if(ok(a[i],b[j])==0) return 0;
		}
		int ip=1,jp=1;
		for(;a[ip]!=-1;ip++,jp++){
			if(a[ip]==-1) break;
			if(ok(a[ip],b[jp])==0) return 0;
		}
		return resolve(i,j,ip,jp);
	}
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	fm[0]=1;
	for(int i=1;i<=100000;i++) fm[i]=fm[i-1]*mul%mod;
	cin>>s>>n;
	ls=s.size();
	s=" "+s;
	for(int i=1;i<=ls;i++){
		if(s[i]=='*'){
			a[i]=-1;
			sts++;
		}else if(s[i]!='?')  a[i]=s[i]-'a'+1;
	}
	for(int i=1;i<=n;i++){
		cin>>t;
		len=t.size();
		t=" "+t;
		for(int j=1;j<=len;j++){
			b[j]=t[j]-'a'+1;
		}
		int flag=solve();
		if(flag) cout<<"YES\n";
		else cout<<"NO\n";
	}
    return 0;
}

喵