Asterisk-Minor Template

题意翻译

定义一个字符串的模板 $T$，其中仅包含小写字母和可以代替任意字符串（包括空字符串）的通配符 '\*'。一个合法的模板需要满足 '\*' 的数量小于等于小写字母的数量。 有一个仅包含小写字母的字符串 $s$，如果我们可以选择出一个合法的模板 $T$，可以通过替换所有的 '\*' 使其等于 $s$，则称字符串 $s$ 与模板 $T$ 匹配。 现在有 $t$ $(1 \le t \le 10^4) $ 组询问，每次给出两个仅包含小写字母的字符串 $a,b$ $(1\le|a|,|b|\le 50)$，请给出一个合法的模板 $T$ 使其能同时匹配两个字符串，或输出无解 "NO"。

题目描述

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 $ ).

题目大意：
给定两个只包含小写字母的字符串 a 和 b。定义一个模板 T，它包含小写字母和可以代替任意字符串（包括空字符串）的通配符 '\*'。一个合法的模板需要满足 '\*' 的数量小于等于小写字母的数量。如果可以通过替换 T 中的所有 '\*' 使其等于 s，则称字符串 s 与模板 T 匹配。现在有 t 组询问，每次给出两个字符串 a 和 b，请给出一个合法的模板 T 使其能同时匹配两个字符串，或输出无解 "NO"。

输入输出数据格式：
输入格式：
- 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。
- 每个测试用例有两行，第一行包含一个字符串 a (1 ≤ |a| ≤ 50)，第二行包含一个字符串 b (1 ≤ |b| ≤ 50)，a 和 b 都只包含小写拉丁字母。

输出格式：
- 对于每个测试用例，如果不存在一个合法的模板 T 能同时匹配 a 和 b，则输出 "NO"。否则，第一行输出 "YES"，第二行输出模板 T。如果有多个答案，输出其中任意一个。
- 模板 T 只能包含小写拉丁字母和 '\*'，且 '\*' 的数量小于等于小写字母的数量。

输入输出样例：
输入样例 #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）。题目大意： 给定两个只包含小写字母的字符串 a 和 b。定义一个模板 T，它包含小写字母和可以代替任意字符串（包括空字符串）的通配符 '\*'。一个合法的模板需要满足 '\*' 的数量小于等于小写字母的数量。如果可以通过替换 T 中的所有 '\*' 使其等于 s，则称字符串 s 与模板 T 匹配。现在有 t 组询问，每次给出两个字符串 a 和 b，请给出一个合法的模板 T 使其能同时匹配两个字符串，或输出无解 "NO"。 输入输出数据格式： 输入格式： - 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。 - 每个测试用例有两行，第一行包含一个字符串 a (1 ≤ |a| ≤ 50)，第二行包含一个字符串 b (1 ≤ |b| ≤ 50)，a 和 b 都只包含小写拉丁字母。 输出格式： - 对于每个测试用例，如果不存在一个合法的模板 T 能同时匹配 a 和 b，则输出 "NO"。否则，第一行输出 "YES"，第二行输出模板 T。如果有多个答案，输出其中任意一个。 - 模板 T 只能包含小写拉丁字母和 '\*'，且 '\*' 的数量小于等于小写字母的数量。 输入输出样例： 输入样例 #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）。