[Cqoi2014]通配符匹配
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 541 Solved: 235[][][]Description
几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个
是星号(“”’)，可以匹配0个及以上的任意字符：另一个是问号(“？”)，可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。Input
第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数n，表示文件个数。接下来n行，每行为一个仅包含小写字母字符串，表示文件名列表。
Output
输出n行，每行为“YES”或“NO”，表示对应文件能否被通配符匹配。
Sample Input
*aca?ctc 6 acaacatctc acatctc aacacatctc aggggcaacacctc aggggcaacatctc aggggcaacctct
Sample Output
YES YES YES YES YES NO
HINT
对于1 00%的数据
·字符串长度不超过1 00000 · 1 <=n<=100 ·通配符个数不超过10
Source
DP+哈希
f[i][j]表示第i个通配符和第j个字符能否匹配，然后搞搞转移，注意两种通配符的区别。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define ULL unsigned long long 8 #define MAXN 100010 9 #define BASE 13110 char S[MAXN],s[MAXN];11 ULL hash[2][MAXN],bin[MAXN];12 int p[20],t,N;13 bool f[12][MAXN];14 inline void Hashtable(char str[],int opt)15 {16 int len=strlen(str+1);17 for (int i=1; i<=len; i++) hash[opt][i]=hash[opt][i-1]*BASE+str[i];18 }19 inline ULL GetHash(int l,int r,int opt)20 {21 return r>l? hash[opt][r]-hash[opt][l-1]*bin[r-l+1] : -1;22 }23 int main()24 {25 bin[0]=1; for (int i=1; i<=MAXN-1; i++) bin[i]=bin[i-1]*BASE;26 scanf("%s",S+1); Hashtable(S,0);27 int len=strlen(S+1);28 for (int i=1; i<=len; i++) if (S[i]=='*' || S[i]=='?') p[++t]=i;29 p[++t]=++len; S[len]='?';30 scanf("%d",&N);31 while (N--)32 {33 scanf("%s",s+1); Hashtable(s,1);34 memset(f,0,sizeof(f)); f[0][0]=1;35 int len=strlen(s+1); s[++len]='@';36 for (int i=0; i<=t-1; i++)37 {38 if (S[p[i]]=='*') for (int j=1; j<=len; j++) if (f[i][j-1]) f[i][j]=1;39 for (int j=0; j<=len; j++)40 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))41 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;42 }43 if (f[t][len]) puts("YES"); else puts("NO");44 }45 return 0;46 }