通配符匹配(Wildcard Matching)
通配符匹配(Wildcard Matching)
题目描述
几乎所有操作系统的命令行界面（CLI）中都支持文件名的通配符匹配以方便用户。最常见的通配符有两个，一个是星号（*），可以匹配 0 个及以上的任意字符；另一个是问号（?），可以匹配恰好一个任意字符。现在需要你编写一个程序，对于给定的文件名列表和一个包含通配符的字符串，判断哪些文件可以被匹配。
输入格式
第一行是一个由小写字母和上述通配符组成的字符串。第二行包含一个整数 ，表示文件个数。接下来 行，每行为一个仅包含小写字母字符串，表示文件名列表。
输出格式
输出 行，每行为 YES 或 NO，表示对应文件能否被通配符匹配。
样例输入 #1
*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct
样例输出 #1
YES
YES
YES
YES
YES
NO
数据范围
对于 的数据
- 字符串长度不超过
- 通配符个数不超过
知识点与难度
本题涉及的知识点从属于 CSP-S，难度（CF Rating）：2000。
测试点分布
| Subtask | 分值 | 测试点编号 | 说明 |
|---|---|---|---|
| 0 | 10 | 1 | 样例 |
| 1 | 20 | 2~7 | 小规模 串长≤500,n≤20 / 特殊: 不含任何通配符精确匹配 / 特殊: 模式串全为*与?组合 |
| 2 | 8~13 | 中等规模 串长≤10000,n≤50 / Hack: 连续多个与?交替及尾部无强约束后缀匹配 | |
| 3 | 25 | 14~19 | 大规模 模式串长≤100000,n≤80,通配符=10 双哈希加速分块DP测试 |
| 4 | 20~25 | 满规模 单串长可达100000,n=100,通配符=10 高重复周期串极限压力测试 |
出处：原题链接