好久没有做过字符串哈希的题，没想到竟然调了这么久。
首先我们可以母串根据？或者星号分为几段，这里有一个小技巧，可以给母串前面加一个？后面加一个a，然后在要匹配的串前后各加一个a
f[i][j]表示母串到了第i个，匹配的串到第j个位置。
那么有两种情况
第一种是？，f[i][j]=f[i-1][j-len]
第二种是星号，f[i][j]|=f[i-1][j-len-k]
然后用哈希判断相应字符串是否相等。
但是这样会TLE，我们需要对第二种情况进行优化。
设v[x]，表示当*对应的长度为x的时候是否可以，每次更新一下即可。
点击查看代码
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
using namespace std;
typedef unsigned long long ll;
const int N=1e5+5;
char s[N],t[N];
bool f[15][N],v[N];
ll h1[N],h2[N],h3[N],h4[N],p1[N],p2[N];
int n,l,tot,a[N],len,x[N],y[N],z[N];
ll num1,num2,num3,num4;
int sum[N];
bool pd(int x,int y,int z,int w){
num1=h1[y]-h1[x-1]*p1[y-x+1];
num2=h2[y]-h2[x-1]*p2[y-x+1];
num3=h3[w]-h3[z-1]*p1[y-x+1];
num4=h4[w]-h4[z-1]*p2[y-x+1];
return (num1==num3 && num2==num4);
}
int main(){
// freopen("data.in","r",stdin);
scanf("%s",s+1);
l=strlen(s+1);
p1[0]=1ll; p2[0]=1ll;
fo(i,1,1e5){
p1[i]=p1[i-1]*(ll)13;
p2[i]=p2[i-1]*(ll)1331;
}
s[0]='?'; s[l+1]='a'; l++;
fo(i,0,l) {
if (s[i]=='?' || s[i]=='*') {
a[++tot]=i;
}
}
fo(i,1,tot-1){
x[i]=s[a[i]]=='*'? 2:1;
y[i]=a[i+1]-a[i]-1;
z[i]=a[i]+1;
}
x[tot]=s[a[tot]]=='*'? 2:1;
y[tot]=l-a[tot];
z[tot]=a[tot]+1;
fo(i,1,l){
if (s[i]=='*' || s[i]=='?') continue;
h1[i]=h1[i-1]*(ll)13+(s[i]-'a'+1);
h2[i]=h2[i-1]*(ll)1331+(s[i]-'a'+1);
}
fo(i,1,tot) sum[i]=sum[i-1]+y[i];
// fo(i,1,tot) printf("%d %d %d\n",x[i],y[i],z[i]);
scanf("%d",&n);
while (n--){
// memset(h3,0,sizeof(h3)); // s[i]==* / ? h3[]=0
// memset(h4,0,sizeof(h4));
memset(f,0,sizeof(f));
scanf("%s",t+1);
len=strlen(t+1);
t[0]='a'; t[len+1]='a'; len++;
h3[0]=h4[0]=1;
fo(i,1,len){
h3[i]=h3[i-1]*(ll)13+(t[i]-'a'+1);
h4[i]=h4[i-1]*(ll)1331+(t[i]-'a'+1);
}
// printf("%d",pd(1,1,1,1));
// return 0;
f[1][y[1]]=pd(1,y[1],1,y[1]);
if (!f[1][y[1]]) {
puts("NO"); continue;
}
memset(v,0,sizeof(v));
fo(i,y[1],len) v[i]=1;
fo(i,2,tot) {
fo(j,1,len){
if (x[i]==1 && j-y[i]-1>=0)
f[i][j]|=f[i-1][j-y[i]-1]&&pd(z[i],z[i]+y[i]-1,j-y[i]+1,j);
if (x[i]==2 && j>=y[i]) {
f[i][j]|=v[j-y[i]]&&pd(z[i],z[i]+y[i]-1,j-y[i]+1,j);
}
}
v[0]=0;
fo(j,1,len) v[j]=v[j-1]|f[i][j];
}
if (f[tot][len]) puts("YES");
else puts("NO");
}
return 0;
}