JS's Blog
0%

Posted on Edited on In ,

题目链接：
http://codeforces.com/contest/832/problem/B

题目大意：
给定一个匹配串A，和许多待匹配串，询问每次两个串之间是否完全匹配，其中给出good character字符集，字符只能与字符匹配，？只能与一个good字符匹配，*可以与空串或者bad character组成的串匹配

分析：
直接模拟即可，可以分成匹配串有*和没有*两种情况，没有*的话，可以特判长度不相等的时候之间跳出，存在*号的话，也可以加个带匹配串长度小于匹配串长度-1时直接输出NO的特判

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>

using namespace std;

int  gd[200];
char gdl[200];
char str[120000];
char query[120000];
int n;




int main()
{
    int pos = -1;
    scanf("%s",gdl);
    for (int i = 0 ; gdl[i] ; i ++)
        gd[gdl[i]]=1;
    scanf("%s",str);
    int len = strlen(str);
    for (int i = 0 ; i< len ; i ++)
        if (str[i]=='*')
        {
            pos = i;
            break;
        }
    scanf("%d",&n);
    for (int i = 1; i <= n ; i ++)
    {
        scanf("%s",query);
        int lq = strlen(query);
        
        int cnt = 0,f=1,fal = len-1;
        if (pos==-1)
        {
            if (lq!=len)
            {
                printf("NO\n");
                continue;
            }
            for (int j = 0 ; j < lq ; j ++)
            {
                if (str[cnt]=='?')
                {
                    if (gd[query[j]]==0)
                    {
                        f= 0 ;
                        break;
                    }
                    else
                        cnt++;
                }
                else
                {
                    if (query[j]!=str[cnt])
                    {
                        f = 0;
                        break;
                    }
                    else
                        cnt++;
                }
            }
        }
        else
        {
            
            if (lq<len-1)
            {
                printf("NO\n");
                continue;
            }
            for (int j = 0 ; j < pos ; j ++)
            {
                if (str[cnt]=='?')
                {
                    if (gd[query[j]]==0)
                    {
                        f=0;
                        break;
                    }
                    else
                        cnt++;
                }
                else
                {
                    if (query[j]!=str[cnt])
                    {
                        f= 0 ;
                        break;
                    }
                    else
                        cnt++;
                }
            }

            int s = lq -1;
            for (int j = len-1; j >= pos +1 ; j --)
            {
                if (str[j]=='?')
                {
                    if (gd[query[s]]==0)
                    {
                        f = 0;
                        break;
                    }
                    else
                        s --;
                }
                else
                {
                    if (str[j]!=query[s])
                    {
                        f = 0;
                        break;

                    }
                    else
                        s--;
                }
            }
            for (int j = pos ; j <= s ;j ++)
            {
                if (gd[query[j]])
                {
                    f= 0;
                    break;
                }
            }
        }

        if (f)
            printf("YES\n");
        else
            printf("NO\n");
    }

    return 0;
}