1796B.md (2548B)
1 Source: https://codeforces.com/problemset/problem/1796/B 2 3 B. Asterisk-Minor Template 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two strings $a$ and $b$, consisting of lowercase Latin letters. 22 23 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. 24 25 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$. 26 27 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. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases. 32 33 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. 34 35 The second line contains a string $b$ ($1 \le |b| \le 50$), consisting of lowercase Latin letters. 36 37 Output 38 39 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. 40 41 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. 42 43 Example 44 45 Input 46 47 ``` 48 6 49 50 aaab 51 52 zzzb 53 54 codeforces 55 56 atcoder 57 58 codeforces 59 60 tokitlx 61 62 aaaa 63 64 aaaaaa 65 66 abcd 67 68 abcd 69 70 c 71 72 f 73 ``` 74 75 Output 76 77 ``` 78 YES 79 *b 80 YES 81 *co* 82 NO 83 YES 84 a*a*a*a 85 YES 86 abcd 87 NO 88 ``` 89 90 Note 91 92 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$). 93 94 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. 95 96 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$). 97 98 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$).