codeforces #425 B. Petya and Exam (暴力)
题意：
给出由小写字母，'?'和'*'组成的字符串s，仅由小写字母组成的字符串t,问按照规则s能否变成t.
规则如下：首先给出定义的[好字母]的字符串，[好字母]之外的都是[坏字母],对于s中每个‘?’，规定其必须替换为一个[好字母]
对于s中的每个‘*’，规定其必须替换为0个或者多个坏字母。
思路：
显然带的会比较难搞。所以只说带的情况
我WA了好多次，原因是一开始读错题（或者题意不太清楚？），认为*只能最多替换一个[坏字母]
后来在这个思路上改，越改越复杂orz
仔细想一下，关键点有两个，一个是当前位置有三种情况{没有经过*,经过且仍在的作用域内，经过且已经出了的作用域}
如何知道的作用域呢？由于的替换是连续的，因此只要对比s和t的长度差就可以了。
对于不同的作用域，普通字母的判断位置是不同的，在经过*的作用域之后，普通字母（包括‘？’）记得加一个offset
所以第二个关键点就是，对于*的替换，一次判断完多个。
除此之外，注意下*可能为空的特殊情况，特判一下比较保险。
/* ***********************************************
Author :111qqz
Created Time :Mon 24 Jul 2017 10:32:44 PM CST
File Name :B.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6string good;
7int len,len2;
8vector<char>go;
9string st;
10int n;
11string tmp;
12vector<int>zimu; //字母的位置
13vector<int>fuhao; //符号的位置
14bool star;
15bool vis[26];
16bool solve()
17{
18 len2 = tmp.length();
19 if (!star)
20 {
21 if (len2!=len) return false;
22 for ( int i = 0 ; i < len2 ; i++)
23 {
24 if (st[i]=='?')
25 {
26 if (!vis[tmp[i]-'a']) return false;
27 }else
28 {
29 if (st[i]!=tmp[i]) return false;
30 }
31 }
32 return true;
33 }
34 if (star)
35 {
1 int stat = 0; //0表示没有经过*,1表示在*的作用域内，-1表示经过了*的作用域
2 if (len2>=len)
3 {
4 int num = len2-len+1; //*匹配的字母个数
5 int offset = num;
6 // cout<<"num:"<<num<<endl;
7 for ( int i = 0 ; i < len ; i++)
8 {
9 if (st[i]=='*')
10 {
11 stat = 1;
12 }
13 if (1==stat) //遇*一次判断完
14 {
15 for ( int j = i ; j < i+num ; j++)
16 if (vis[tmp[j]-'a']) return false;
17 stat = -1;
18 }
1 if(st[i]=='?')
2 {
3 if (0 == stat)
4 {
5 if (!vis[tmp[i]-'a']) return false;
6 }
7 if (-1 == stat)
8 {
9 if (!vis[tmp[i+offset-1]-'a']) return false;
10 }
11 }
12 if (st[i]!='?'&&st[i]!='*')
13 {
14 if (0==stat)
15 {
16 if (st[i]!=tmp[i]) return false;
17 }
18 if (-1==stat)
19 {
20 if (st[i]!=tmp[i+offset-1]) return false; //记得*造成的偏移，却只考虑了*表示一个字母时的偏移...orz
21 }
22 }
23 }
24 //区分*经过前和后的两种状态
25 return true;
26 }
27 else if (len2==len-1) //*替换为空
28 {
29 bool flag = false;
30 for ( int i = 0 ; i < len2 ; i++)
31 {
32 int cur = i;
33 if (st[cur]=='*') flag = true;
34 if (flag) cur = i+1;
35 if (st[cur]=='?')
36 {
37 if (!vis[tmp[i]-'a']) return false;
38 }else
39 {
40 if (st[cur]!=tmp[i]) return false;
41 }
42 }
43 }else return false;
1 }
2 return true;
3}
4int main()
5{
6#ifndef ONLINE_JUDGE
7 freopen("./in.txt","r",stdin);
8#endif
1 ms(vis,false);
2 cin>>good;
3 len = good.length();
4 for ( int i = 0 ; i < len ; i++) vis[good[i]-'a'] = true;
1 cin>>st;
2 len = st.length();
3 star = false;
4 for ( int i = 0 ; i < len ; i++) if (st[i]=='*') star = true;
5 cin>>n;
6 for ( int i = 1 ; i <= n ; i++)
7 {
8 cin>>tmp;
9 bool ok = solve();
10 if (ok) puts("YES");
11 else puts("NO");
12 }
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}