题意：给你两个串，第一个串里面的字母都是good 字母，
第二个串是模式串，里面除了字母还有？和*（只有一个）
？可以替换所有good字母， *可以替换所有坏字母和空格（可以是多个坏字母！！！这点卡了我很久，也不举一个样例。。。）
然后q次询问，每次给你一个串，问你能否匹配成功，yes or no
思路：暴力，可惜晚上的时候被hacks掉了，真实数据的范围是超过1e5的，比较可惜。
#include <stdio.h>
#include <string.h>
#include <vector>
#include<math.h>
#include <algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define MAXSIZE 1000005
#define LL long long
using namespace std; int vis[MAXSIZE]; int solve(char s1[],char s2[],int index)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
if(len1 > len2 + )
return ;
int id;
if(index == -)
{
if(len1 != len2)
return ;
for(int i=;i<len1;i++)
{
if(s1[i] == '?')
{
id = s2[i] - 'a';
if(!vis[id])
return ;
} else if(s1[i] != s2[i])
return ;
}
return ;
} else
{
int pos1,pos2;
if(len1 - len2 == )
{
pos1 = ;
pos2 = ;
while(pos1<len1 && pos2<len2)
{
if(s1[pos1] == '*')
{
pos1++;
continue;
}
if(s1[pos1] == '?')
{
int id = s2[pos2] - 'a';
if(!vis[id])
return ;
}
else if(s1[pos1] != s2[pos2])
{
return ;
}
pos1++;
pos2++;
}
return ;
}
int s=-,e=-;
for(int i1=,i2=;i1<len1 && i2<len2;i1++,i2++)
{
id = s2[i2] - 'a';
if(!vis[id] && (s1[i1] != s2[i1]))
{
s = i2;
break;
}
} for(int i1=len1-,i2=len2-;i1>= && i2>=;i1--,i2--)
{
id = s2[i2] - 'a';
if(!vis[id] && (s1[i1] != s2[i2]))
{
e = i2;
break;
}
} if(s==- || e==-)
return ; pos1 = ;
pos2 = ;
while(pos1<index && pos2<s)
{
if(s1[pos1] == '?')
{
pos1++;
pos2++;
continue;
} if(s1[pos1] != s2[pos2])
return ;
pos1++;
pos2++;
}
if(pos1 != pos2 || pos1!=s)
return ;
pos1++;
while(pos2<=e)
{
id = s2[pos2] - 'a';
if(vis[id])
return ;
pos2++;
}
while(pos1<len1 && pos2<len2)
{
if(s1[pos1] == '?')
{
pos1++;
pos2++;
continue;
}
else if(s1[pos1] != s2[pos2])
return ;
pos1++;
pos2++;
}
if(pos1!=len1 || pos2!=len2)
return ;
return ;
}
} int main()
{
int n,len,index=-;
char s1[MAXSIZE],s2[MAXSIZE];
cin >> s1;
len = strlen(s1);
for(int i=;i<len;i++)
{
int id = s1[i] - 'a';
vis[id] = ;
}
cin >> s1;
len = strlen(s1);
for(int i=;i<len;i++)
{
if(s1[i] == '*')
{
index = i;
break;
}
}
scanf("%d",&n);
while(n--)
{
cin >> s2;
int ok = solve(s1,s2,index);
if(ok)
printf("YES\n");
else
printf("NO\n");
}
return ;
}