‹ 上一题 下一题 ›

j02125. 通配符匹配 未做

1000 ms 256 MB 测试点 10 线性DPJ·复赛必做100题自拟题r2一维动态规划

题目描述

文件检索支持通配符:模式串由小写字母、?、* 组成,? 恰好匹配任意一个字符, * 匹配任意一串字符(可以为空)。判断模式串能否匹配给定文本。多组查询。

输入格式

第一行一个整数 ;接下来每条查询两行:第一行模式串,第二行文本 (均非空,文本只含小写字母)。

输出格式

每条查询输出一行 YES 或 NO。

样例

输入
4
a*b
axxyb
a?b
acb
a?b
ab
*abc*
xxabcxx
输出
YES
YES
NO
YES

数据范围

  • 对于 30% 的数据,模式串不含 *。
  • 对于 60% 的数据,单条 |模式|, |文本| 200。
  • 对于 100% 的数据,1 1000,|模式|, |文本| 1000,且单组数据所有查询的 |模式||文本| 之和 。
输入
输出

            
答案