← 返回题目列表

Codeforces · 1796/B

B. 星号-小模板

中文机器翻译题面 查看原题

给定两个字符串 $$$a$$$ 和 $$$b$$$,由小写拉丁字母组成。

模板 $$$t$$$ 是字符串,由小写拉丁字母和星号(字符“*”)组成。如果模板中星号的数量小于或等于其中字母的数量,则该模板称为星号次要模板。

如果您可以将 $$$t$$$ 中的每个星号替换为小写拉丁字母字符串(可能是空字符串),使其等于 $$$s$$$,则称字符串 $$$s$$$ 与模板 $$$t$$$ 匹配。

查找一个星号小模板,使 $$$a$$$ 和 $$$b$$$ 与其匹配,或者报告此类模板不存在。如果有多个答案,请打印其中任何一个。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个字符串 $$$a$$$ ($$$1 \le |a| \le 50$$$,其中 $$$|a|$$$ 是 $$$a$$$ 的长度),由小写拉丁字母组成。

第二行包含一个字符串 $$$b$$$ ($$$1 \le |b| \le 50$$$),由小写拉丁字母组成。

输出

对于每个测试用例,如果不存在 $$$a$$$ 和 $$$b$$$ 匹配的星号小模板,则输出“NO”。否则,在第一行打印“YES”,在第二行打印模板。如果有多个答案,请打印其中任何一个。

模板应仅包含小写拉丁字母和星号(字符“*”)。星号的数量应小于或等于字母的数量。

示例

输入 #1

6
aaab
zzzb
codeforces
atcoder
codeforces
tokitlx
aaaa
aaaaaa
abcd
abcd
c
f

输出 #1

YES
*b
YES
*co*
NO
YES
a*a*a*a
YES
abcd
NO

注意

在第一个测试用例中,对于模板“*b”,您可以将唯一的星号替换为“aaa”以获得“aaab”(等于$$$a$$$)或用“zzz”替换为“zzzb”(等于$$$b$$$)。

在第三个测试用例中,模板“*o*”不是星号次要的,因为它包含的星号多于字母。没有 $$$a$$$ 和 $$$b$$$ 匹配的小星号模板。

在第四个测试用例中,对于模板“a*a*a*a”,您可以将所有星号替换为空字符串以获得“aaaa”(等于$$$a$$$),或者将其中两个星号替换为“a”,其中两个星号替换为空字符串以获得“aaaaaa”(等于$$$b$$$)。

在第五个测试用例中,模板“abcd”中没有星号,因此只有“abcd”可以匹配它(巧合的是 $$$a$$$ 和 $$$b$$$)。