BZOJ 3507 [Cqoi2014]通配符匹配 hash 题解

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

题解#

将原字符串由’*‘分成若干段
记录每一个’?‘的位置
分段hash 将文件首尾先匹配然后在中间贪心的匹配

1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-06-17 10:45:09
4
 * @Last Modified by: WildRage
5
 * @Last Modified time: 2017-06-17 11:09:39
6
 */
7
#include<cstdio>
8
#include<cstring>
9
#include<algorithm>
10
#include<vector>
11
#include<stack>
12
using namespace std;
13
#define ULL unsigned long long
14
const ULL base=31;
15
ULL pw[100005],f[15][15],HASH[100005];
16
int pos[15],cnt,num[15],s[15][15],n,lenth;
17
char S[100005],a[100005];
18
ULL get_hash(int l,int r){
19
    return HASH[r]-HASH[l-1]*pw[r-l+1];
20
}
21
bool OK(int i,int k){
22
    for(int j=0;j<=num[k];j++){
23
        if(s[k][j]==0){i++;continue;}
24
        if(f[k][j]!=get_hash(i,i+s[k][j]-1))return 0;
25
        i+=s[k][j]+1;
26
    }
27
    return 1;
28
}
29
bool work(char *b){
30
    int len=strlen(b+1);
31
    if(!cnt){
32
        if(lenth!=len)return 0;
33
        for(int i=1;i<=lenth;i++)
34
            if(S[i]!=b[i]&&S[i]!='?')return 0;
35
        return 1;
36
    }
37
    if(len<(pos[1]-1)+(lenth-pos[cnt]))return 0;
38
    for(int i=1;i<pos[1];i++)if(S[i]!=b[i]&&S[i]!='?')return 0;
39
    for(int i=lenth,j=len;i>pos[cnt];i--,j--)
40
        if(S[i]!=b[j]&&S[i]!='?')return 0;
41
    for(int i=1;i<=len;i++) HASH[i]=HASH[i-1]*base+b[i];
42
    int MAX=len-(lenth-pos[cnt])+1;
43
    int i=pos[1];
44
    for(int k=2;k<=cnt;k++){
45
        while(i<=MAX){
46
            if(OK(i,k))break;
47
            i++;
48
        }
49
        i+=pos[k]-pos[k-1]-1;
50
        if(i>MAX) return 0;
51
    }
52
    return 1;
53
}
54
int main()
55
{
56
    //freopen("match.in","r",stdin);
57
    //freopen("match.out","w",stdout);
58
    scanf("%s",S+1);
59
    lenth=strlen(S+1);
60
    pw[0]=1;
61
    cnt=0;
62
    for(int i=1;i<=100000;i++)pw[i]=pw[i-1]*base;
63
    for(int i=1;i<=lenth;i++)
64
        if(S[i]=='*')
65
            pos[++cnt]=i;
66
    for(int i=2;i<=cnt;i++){
67
        num[i]=0;
68
        for(int j=pos[i-1]+1;j<pos[i];j++){
69
            if(S[j]=='?'){
70
                num[i]++;
71
                continue;
72
            }
73
            s[i][num[i]]++;
74
            f[i][num[i]]=f[i][num[i]]*base+S[j];
75
        }
76
    }
77
    scanf("%d",&n);
78
    while(n--){
79
        scanf("%s",a+1);
80
        if(work(a))puts("YES");
81
        else puts("NO");
82
    }
83
    //while(1);
84
}