codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```