1999D.md (1859B)
1 Source: https://codeforces.com/problemset/problem/1999/D 2 3 D. Slavic's Exam 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 Slavic has a very tough exam and needs your help in order to pass it. Here is the question he is struggling with: 22 23 There exists a string $s$, which consists of lowercase English letters and possibly zero or more "?". 24 25 Slavic is asked to change each "?" to a lowercase English letter such that string $t$ becomes a subsequence (not necessarily continuous) of the string $s$. 26 27 Output any such string, or say that it is impossible in case no string that respects the conditions exists. 28 29 Input 30 31 The first line contains a single integer $T$ ($1 \leq T \leq 10^4$) — the number of test cases. 32 33 The first line of each test case contains a single string $s$ ($1 \leq |s| \leq 2 \cdot 10^5$, and $s$ consists only of lowercase English letters and "?"-s) – the original string you have. 34 35 The second line of each test case contains a single string $t$ ($1 \leq |t| \leq |s|$, and $t$ consists only of lowercase English letters) – the string that should be a subsequence of string $s$. 36 37 The sum of $|s|$ over all test cases doesn't exceed $2 \cdot 10^5$, where $|x|$ denotes the length of the string $x$. 38 39 Output 40 41 For each test case, if no such string exists as described in the statement, output "NO" (without quotes). 42 43 Otherwise, output "YES" (without quotes). Then, output one line — the string that respects all conditions. 44 45 You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", and "Yes" will be recognized as a positive response). 46 47 If multiple answers are possible, you can output any of them. 48 49 Example 50 51 Input 52 53 ``` 54 5 55 56 ????? 57 58 xbx 59 60 ab??e 61 62 abcde 63 64 ayy?x 65 66 a 67 68 ab??e 69 70 dac 71 72 paiu 73 74 mom 75 ``` 76 77 Output 78 79 ``` 80 YES 81 xabax 82 YES 83 abcde 84 YES 85 ayyyx 86 NO 87 NO 88 ```