几乎所有操作系统的命令行界面(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 131char S[MAXN],s[MAXN];ULL hash[2][MAXN],bin[MAXN];int p[20],t,N;bool f[12][MAXN];inline void Hashtable(char str[],int opt){    int len=strlen(str+1);    for (int i=1; i<=len; i++) hash[opt][i]=hash[opt][i-1]*BASE+str[i];}inline ULL GetHash(int l,int r,int opt){    return r>l? hash[opt][r]-hash[opt][l-1]*bin[r-l+1] : -1;}int main(){    bin[0]=1; for (int i=1; i<=MAXN-1; i++) bin[i]=bin[i-1]*BASE;    scanf("%s",S+1); Hashtable(S,0);    int len=strlen(S+1);    for (int i=1; i<=len; i++) if (S[i]==‘*‘ || S[i]==‘?‘) p[++t]=i;    p[++t]=++len; S[len]=‘?‘;//    for (int i=1; i<=t; i++) printf("%d   %c\n",p[i],S[p[i]]);    scanf("%d",&N);    while (N--)        {            scanf("%s",s+1); Hashtable(s,1);            memset(f,0,sizeof(f)); f[0][0]=1;            int len=strlen(s+1); s[++len]=‘@‘;            for (int i=0; i<=t-1; i++)                {                    if (S[p[i]]==‘*‘) for (int j=1; j<=len; j++) if (f[i][j-1]) f[i][j]=1;                    for (int j=0; j<=len; j++)                        if (f[i][j] && GetHash(j+1,j+(p[i+1]-1)-(p[i]+1)+1,1)==GetHash(p[i]+1,p[i+1]-1,0))                            if (S[p[i+1]]==‘?‘) f[i+1][j+(p[i+1]-1)-(p[i]+1)+1+1]=1; else f[i+1][j+(p[i+1]-1)-(p[i]+1)+1]=1;                }            if (f[t][len]) puts("YES"); else puts("NO");        }    return 0;}