题目
几乎所有操作系统的命令行界面(CLI)中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个
是星号(“”’)，可以匹配0个及以上的任意字符：另一个是问号(“？”)，可以匹配恰好一个任意字符。
现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。
输入格式
第一行是一个由小写字母和上述通配符组成的字符串。
第二行包含一个整数n，表示文件个数。
接下来n行，每行为一个仅包含小写字母字符串，表示文件名列表。
输出格式
输出n行，每行为“YES”或“NO”，表示对应文件能否被通配符匹配。
输入样例
*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct
输出样例
YES
YES
YES
YES
YES
NO
提示
对于1 00%的数据
·字符串长度不超过1 00000
· 1 <=n<=100
·通配符个数不超过10
题解
由于通配符很少，我们可以将原串按\(*\)分成若干段，每段为由?隔开的若干个字符串
然后用hash贪心匹配即可
细节极多
最重要的是记得考虑两端是否有\(*\)
码力不足的蒟蒻我已累瘫
还有我丑陋的代码
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
#define ULL unsigned long long int
using namespace std;
const int maxn = 100005,maxm = 100005,INF = 1000000000;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
ULL P[maxn];
char T[maxn];
int tot,L[maxn],n;
vector<ULL> hash[maxn];
vector<int> len[maxn];
int head,tail;
void init(){
P[0] = 1;
for (int i = 1; i <= 100000; i++) P[i] = P[i - 1] * 107;
scanf("%s",T + 1);
n = strlen(T + 1);
if (T[1] == '*') head = true;
if (T[n] == '*') tail = true;
for (int i = 1; i <= n; i++){
if (T[i] == '*') continue;
tot++;
LL h = 0;
for (int j = i; j; j++){
if (j > n || T[j] == '*'){
hash[tot].push_back(h);
len[tot].push_back(j - i);
i = j;
break;
}
if (T[j] == '?'){
hash[tot].push_back(h);
len[tot].push_back(j - i);
h = 0;
i = j + 1;
continue;
}
h = h * 107 + T[j];
}
}
for (int i = 1; i <= tot; i++){
L[i] = len[i].size() - 1;
for (int j = 0; j < len[i].size(); j++){
L[i] += len[i][j];
}
}
/*for (int i = 1; i <= tot; i++,puts(""))
for (int j = 0; j < len[i].size(); j++)
printf("%d ",len[i][j]);*/
}
char s[maxn];
int m;
ULL h[maxn];
bool cmp(int u,int p){
int t = p;
for (int j = 0; j < len[u].size(); j++){
if (t > m) return false;
int r = t + len[u][j] - 1;
if (r > m) return false;
if (hash[u][j] != h[r] - h[t - 1] * P[len[u][j]]) return false;
t = r + 2;
}
return true;
}
void solve(){
int q = read();
while (q--){
scanf("%s",s + 1);
m = strlen(s + 1);
h[0] = 0;
int l = 1,r = m;
for (int i = 1; i <= m; i++) h[i] = h[i - 1] * 107 + s[i];
if (!head){
if (!cmp(1,1)){
puts("NO");
continue;
}
l = L[1] + 1;
}
if (!tail){
if (!cmp(tot,m - L[tot] + 1)){
puts("NO");
continue;
}
r = m - L[tot];
}
//puts("LXT");
/*if (head && !tail && tot == 1){
puts("YES");
continue;
}
if (!head && tail && tot == 1){
puts("YES");
continue;
}*/
int p = l,i,E = tail ? tot : tot - 1;
for (i = head ? 1 : 2; i <= E && p <= r; i++){
if (cmp(i,p)) p += L[i];
else p++,i--;
}
if (i <= E){
puts("NO");
}
else puts("YES");
}
}
int main(){
init();
solve();
return 0;
}