传送门
AC自动机也可以写的啊，就是判断多了点，思路和KMP的挺像的
具体的可以参考一下这一篇
然后贴一个代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
void read(int &x) {
char ch; bool ok;
for(ok=0,ch=getchar(); !isdigit(ch); ch=getchar()) if(ch=='-') ok=1;
for(x=0; isdigit(ch); x=x*10+ch-'0',ch=getchar()); if(ok) x=-x;
}
#define rg register
const int maxn=1e5+10;vector<int>ed[maxn];queue<int>q;
int id=1,n,m,T,rt,sum,ch[maxn][26],fail[maxn],st[maxn];char s[maxn],ss[maxn],cnt[maxn];
int newnode()
{
id++,fail[id]=0,ed[id].clear();
for(rg int i=0;i<26;i++)ch[id][i]=0;return id;
}
void insert(int l,int r,int d)
{
rt=1;
for(rg int i=l;i<=r;i++)
{
int now=s[i]-'a';
if(!ch[rt][now])ch[rt][now]=newnode();
rt=ch[rt][now];
}
ed[rt].push_back(d);
}
void bfs()
{
q.push(1);
while(!q.empty())
{
int x=q.front();q.pop();
for(rg int i=0;i<26;i++)
{
if(!ch[x][i]){ch[x][i]=fail[x]?ch[fail[x]][i]:1;continue;}
int j=fail[x],z=ch[x][i];q.push(z);
while(j&&!ch[j][i])j=fail[j];
fail[z]=j?ch[j][i]:1;
for(rg int j=0;j<(int)ed[fail[z]].size();j++)ed[z].push_back(ed[fail[z]][j]);
}
}
}
bool get(int l,int r,int now,int d)
{
memset(cnt,0,sizeof cnt);
id=0;rt=newnode();
int end=0,num=0;
for(rg int i=l;i<=r;i++)
if(s[i]!='?')
{
end=i;while(end<=r&&s[end]!='?')end++;end--;
insert(i,end,end-l+1);i=end,num++;
}
bfs();rt=1;
for(rg int i=1;i<=m;i++)
{
int now=ss[i]-'a';rt=ch[rt][now];
if(ed[rt].size())
{
int t=ed[rt].size();
for(rg int j=0;j<t;j++)if(i-ed[rt][j]+1>0)cnt[i-ed[rt][j]+1]++;
}
}
for(rg int i=1;i<=m;i++)
if(cnt[i]==num)
{
if(!sum)
{
if(s[1]!='*'&&!now&&i!=1)continue;
if(s[n]!='*'&&r-l+i!=m&&d)continue;
st[++sum]=r-l+i;return 1;
}
else
{
if(i<=st[sum])continue;
if(s[n]!='*'&&r-l+i!=m&&d)continue;
st[++sum]=r-l+i;return 1;
}
}
return 0;
}
int main()
{
scanf("%s",s+1),read(T),n=strlen(s+1);
while(T--)
{
scanf("%s",ss+1),m=strlen(ss+1);
int end=0,num=0;bool flag=0;sum=0;
for(rg int i=1;i<=n;i++)
if(s[i]!='*')
{
end=i;while(end<=n&&s[end]!='*')end++;end--;
if(!get(i,end,num,end==n)){flag=1;break;}i=end,num++;
}
if(flag)printf("NO\n");else printf("YES\n");
}
}