CF1796B.Asterisk-Minor Template

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

You are given two strings $a$ and $b$ , consisting of lowercase Latin letters.

A template $t$ is string, consisting of lowercase Latin letters and asterisks (character '*'). A template is called asterisk-minor if the number of asterisks in it is less than or equal to the number of letters in it.

A string $s$ is said to be matching a template $t$ if you can replace each asterisk in $t$ with a string of lowercase Latin letters (possibly, an empty string) so that it becomes equal to $s$ .

Find an asterisk-minor template such that both $a$ and $b$ match it, or report that such a template doesn't exist. If there are multiple answers, print any of them.

输入格式

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) — the number of testcases.

The first line of each testcase contains a string $a$ ( $1 \le |a| \le 50$ , where $|a|$ is the length of $a$ ), consisting of lowercase Latin letters.

The second line contains a string $b$ ( $1 \le |b| \le 50$ ), consisting of lowercase Latin letters.

输出格式

For each testcase, output "NO", if there doesn't exist an asterisk-minor template that both $a$ and $b$ match. Otherwise, print "YES" in the first line and the template in the second line. If there are multiple answers, print any of them.

A template should consist only of lowercase Latin letters and asterisks (character '*'). The number of asterisks should be less than or equal to the number of letters.

输入输出样例

输入#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

说明/提示

In the first testcase, for a template "*b", you can replace the only asterisk with "aaa" to get "aaab" (which is equal to $a$ ) or with "zzz" to get "zzzb" (which is equal to $b$ ).

In the third testcase, a template "*o*" is not asterisk-minor, as it contains more asterisks than letters. There are no asterisk-minor templates that both $a$ and $b$ match.

In the fourth testcase, for a template "a*a*a*a", you can replace all asterisks with empty strings to get "aaaa" (which is equal to $a$ ) or two of them with "a" and two of them with an empty string to get "aaaaaa" (which is equal to $b$ ).

In the fifth testcase, there are no asterisks in a template "abcd", so only "abcd" can match it (which is coincidentally both $a$ and $b$ ).

首页