codeforces #425 B. Petya and Exam (暴力)
题意：
给出由小写字母，’?‘和’*‘组成的字符串s，仅由小写字母组成的字符串t,问按照规则s能否变成t.
规则如下：首先给出定义的[好字母]的字符串，[好字母]之外的都是[坏字母],对于s中每个‘?’，规定其必须替换为一个[好字母]
对于s中的每个‘*’，规定其必须替换为0个或者多个坏字母。
思路：
显然带的会比较难搞。所以只说带的情况
我WA了好多次，原因是一开始读错题（或者题意不太清楚？），认为*只能最多替换一个[坏字母]
后来在这个思路上改，越改越复杂orz
仔细想一下，关键点有两个，一个是当前位置有三种情况{没有经过*,经过且仍在的作用域内，经过且已经出了的作用域}
如何知道的作用域呢？由于的替换是连续的，因此只要对比s和t的长度差就可以了。
对于不同的作用域，普通字母的判断位置是不同的，在经过*的作用域之后，普通字母（包括‘？’）记得加一个offset
所以第二个关键点就是，对于*的替换，一次判断完多个。
除此之外，注意下*可能为空的特殊情况，特判一下比较保险。
1/* ***********************************************
2Author :111qqz
3Created Time :Mon 24 Jul 2017 10:32:44 PM CST
4File Name :B.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34string good;
35int len,len2;
36vector<char>go;
37string st;
38int n;
39string tmp;
40vector<int>zimu; //字母的位置
41vector<int>fuhao; //符号的位置
42bool star;
43bool vis[26];
44bool solve()
45{
46 len2 = tmp.length();
47 if (!star)
48 {
49 if (len2!=len) return false;
50 for ( int i = 0 ; i < len2 ; i++)
51 {
52 if (st[i]=='?')
53 {
54 if (!vis[tmp[i]-'a']) return false;
55 }else
56 {
57 if (st[i]!=tmp[i]) return false;
58 }
59 }
60 return true;
61 }
62 if (star)
63 {
64
65 int stat = 0; //0表示没有经过*,1表示在*的作用域内，-1表示经过了*的作用域
66 if (len2>=len)
67 {
68 int num = len2-len+1; //*匹配的字母个数
69 int offset = num;
70 // cout<<"num:"<<num<<endl;
71 for ( int i = 0 ; i < len ; i++)
72 {
73 if (st[i]=='*')
74 {
75 stat = 1;
76 }
77 if (1==stat) //遇*一次判断完
78 {
79 for ( int j = i ; j < i+num ; j++)
80 if (vis[tmp[j]-'a']) return false;
81 stat = -1;
82 }
83
84 if(st[i]=='?')
85 {
86 if (0 == stat)
87 {
88 if (!vis[tmp[i]-'a']) return false;
89 }
90 if (-1 == stat)
91 {
92 if (!vis[tmp[i+offset-1]-'a']) return false;
93 }
94 }
95 if (st[i]!='?'&&st[i]!='*')
96 {
97 if (0==stat)
98 {
99 if (st[i]!=tmp[i]) return false;
100 }
101 if (-1==stat)
102 {
103 if (st[i]!=tmp[i+offset-1]) return false; //记得*造成的偏移，却只考虑了*表示一个字母时的偏移...orz
104 }
105 }
106 }
107 //区分*经过前和后的两种状态
108 return true;
109 }
110 else if (len2==len-1) //*替换为空
111 {
112 bool flag = false;
113 for ( int i = 0 ; i < len2 ; i++)
114 {
115 int cur = i;
116 if (st[cur]=='*') flag = true;
117 if (flag) cur = i+1;
118 if (st[cur]=='?')
119 {
120 if (!vis[tmp[i]-'a']) return false;
121 }else
122 {
123 if (st[cur]!=tmp[i]) return false;
124 }
125 }
126 }else return false;
127
128 }
129 return true;
130}
131int main()
132{
133#ifndef ONLINE_JUDGE
134 freopen("./in.txt","r",stdin);
135#endif
136
137 ms(vis,false);
138 cin>>good;
139 len = good.length();
140 for ( int i = 0 ; i < len ; i++) vis[good[i]-'a'] = true;
141
142 cin>>st;
143 len = st.length();
144 star = false;
145 for ( int i = 0 ; i < len ; i++) if (st[i]=='*') star = true;
146 cin>>n;
147 for ( int i = 1 ; i <= n ; i++)
148 {
149 cin>>tmp;
150 bool ok = solve();
151 if (ok) puts("YES");
152 else puts("NO");
153 }
154
155#ifndef ONLINE_JUDGE
156 fclose(stdin);
157#endif
158 return 0;
159}