#P3507. [Cqoi2014]通配符匹配

    ID: 2719 传统题 1000ms 128MiB 尝试: 695 已通过: 278 难度: 6 上传者: 标签>难度分类提高动态规划线性 DP字符串KMP前缀和优化 DP滚动数组CF1900

[Cqoi2014]通配符匹配

[CQOI2014] 通配符匹配

题目描述

给定一个文件名模式,判断哪些文件名与它完全匹配。模式由小写英文字母和以下两种通配符组成。

  • * 可以匹配任意长度的字符串,包括空串。
  • ? 恰好匹配一个任意小写英文字母。

模式中的普通字母只能匹配相同的字母。匹配必须覆盖整个文件名。

输入格式

第一行是模式字符串。第二行一个整数 nn,表示文件个数。接下来 nn 行,每行一个文件名,只含小写英文字母。

输出格式

按照输入顺序,每个文件名输出一行。如果与模式完全匹配,输出 YES,否则输出 NO。

样例 #1

*aca?ctc
6
acaacatctc
acatctc
aacacatctc
aggggcaacacctc
aggggcaacatctc
aggggcaacctct
YES
YES
YES
YES
YES
NO

数据范围

1≤n≤1001\le n\le100。模式和每个文件名的长度都不超过 100000100000。两种通配符在模式中的出现次数合计不超过 1010。