Asterisk-Minor Template (Codeforces 1796B)
Tags: Implement, strings

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.

Input: 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.

Output: 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.

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

Sample Inputs:
6
aaab
zzzb
codeforces
atcoder
codeforces
tokitlx
aaaa
aaaaaa
abcd
abcd
c
f

Sample Outputs:
YES
*b
YES
*co*
NO
YES
a*a*a*a
YES
abcd
NO

Solution (Python):
def solve():
    a = input()
    b = input()
    if a[0] == b[0]:
        print('YES')
        print(f'{a[0]}*')
    elif a[-1] == b[-1]:
        print('YES')
        print(f'*{a[-1]}')
    else:
        for i in range(len(a) - 1):
            if a[i:i + 2] in b:
                print('YES')
                print(f'*{a[i:i + 2]}*')
                return
        print('NO')
for _ in range(int(input())):
    solve()

Solution (Python):
def solve():
    a = input()
    b = input()
    if a[0] == b[0]:
        print('YES')
        print(f'{a[0]}*')
    elif a[-1] == b[-1]:
        print('YES')
        print(f'*{a[-1]}')
    else:
        for i in range(len(a) - 1):
            if a[i:i + 2] in b:
                print('YES')
                print(f'*{a[i:i + 2]}*')
                return
        print('NO')
for _ in range(int(input())):
    solve()

Solution (Python):
def solve():
    a = input()
    b = input()
    if a[0] == b[0]:
        print('YES')
        print(f'{a[0]}*')
    elif a[-1] == b[-1]:
        print('YES')
        print(f'*{a[-1]}')
    else:
        for i in range(len(a) - 1):
            if a[i:i + 2] in b:
                print('YES')
                print(f'*{a[i:i + 2]}*')
                return
        print('NO')
for _ in range(int(input())):
    solve()