几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个
是星号(“”’)，可以匹配0个及以上的任意字符：另一个是问号(“？”)，可以匹配恰好一个任意字符。
现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。

第一行是一个由小写字母和上述通配符组成的字符串。
第二行包含一个整数n，表示文件个数。
接下来n行，每行为一个仅包含小写字母字符串，表示文件名列表。

输出n行，每行为“YES”或“NO”，表示对应文件能否被通配符匹配。

对于1 00%的数据

·字符串长度不超过1 00000

·  1 <=n<=100

·通配符个数不超过10

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 #define ULL unsigned long long

 #define MAXN 100010

 #define BASE 131

 char S[MAXN],s[MAXN];

 ULL hash[][MAXN],bin[MAXN];

 int p[],t,N;

 bool f[][MAXN];

 inline void Hashtable(char str[],int opt)

 {

     int len=strlen(str+);

     for (int i=; i<=len; i++) hash[opt][i]=hash[opt][i-]*BASE+str[i];

 }

 inline ULL GetHash(int l,int r,int opt)

 {

     return r>l? hash[opt][r]-hash[opt][l-]*bin[r-l+] : -;

 }

 int main()

 {

     bin[]=; for (int i=; i<=MAXN-; i++) bin[i]=bin[i-]*BASE;

     scanf("%s",S+); Hashtable(S,);

     int len=strlen(S+);

     for (int i=; i<=len; i++) if (S[i]=='*' || S[i]=='?') p[++t]=i;

     p[++t]=++len; S[len]='?';

     scanf("%d",&N);

     while (N--)

         {

             scanf("%s",s+); Hashtable(s,);

             memset(f,,sizeof(f)); f[][]=;

             int len=strlen(s+); s[++len]='@';

             for (int i=; i<=t-; i++)

                 {

                     if (S[p[i]]=='*') for (int j=; j<=len; j++) if (f[i][j-]) f[i][j]=;

                     for (int j=; j<=len; j++)

                         if (f[i][j] && GetHash(j+,j+(p[i+]-)-(p[i]+)+,)==GetHash(p[i]+,p[i+]-,))

                             if (S[p[i+]]=='?') f[i+][j+(p[i+]-)-(p[i]+)++]=; else f[i+][j+(p[i+]-)-(p[i]+)+]=;

                 }

             if (f[t][len]) puts("YES"); else puts("NO");

         }

     return ;

 }