No.2231 Surprising Flash!
タグ : / 解いたユーザー数 16
作問者 : 👑
akakimidori
Problem Statement
Hachiji-kun has decided to prepare a string $S_1$ consisting of lowercase English letters and give it to a friend as a birthday present.
To surprise the friend, Hachiji-kun tried to make the string $S_1$ so that it contains the string $S_2$ as a contiguous substring. However, Hachiji-kun has forgotten part of the string he was trying to make.
You are given a string $S_1$ of length $N$ consisting of lowercase English letters and ?, where ? indicates that Hachiji-kun has forgotten the character at that position. For Hachiji-kun, replace each ? with a lowercase English letter to restore a string that contains the string $S_2$ of length $M$ as a contiguous substring. If there are multiple such strings, find the lexicographically smallest one among them; if there is no such string, report that.
You are given $T$ test cases; find the answer for each of them.
Input
The input is given from standard input in the following format.
$T$ $case_1$ $case_2$ $\vdots$ $case_T$
Each case is given in the following format.
$N$ $M$ $S_1$ $S_2$
Constraints
- $N, M, T$ are integers.
- $1 \leq T \leq 10^5$
- $1 \leq M \leq N \leq 5 \times 10^5$
- $S_1$ is a string of length $N$ consisting only of lowercase English letters and
?. - $S_2$ is a string of length $M$ consisting only of lowercase English letters.
- For a single input file, the sum of $N$ does not exceed $5 \times 10^5$.
Output
Output over $T$ lines. On the $i(1 \leq i \leq T)$-th line, for the $i$-th test case, output -1 if it is impossible to make the string contain $S_2$ as a contiguous substring by changing the ? positions of $S_1$ to lowercase English letters. If it is possible, output the lexicographically smallest such string.
Sample
Sample 1
Input
4 13 10 g?e??owo??d?d helloworld 26 3 abcdefghijklmnopqrstuvwx?? zzz 10 10 helloworld helloworld 12 3 t?t?r???g?s? kog
Output
ghelloworldad -1 helloworld tatarakogasa
For the first test case, the $2$-nd through $11$-th characters form helloworld, so the string indeed contains helloworld as a contiguous substring. Other strings such as ghelloworldld also contain helloworld as a contiguous substring, but note that you must output the lexicographically smallest one.
For the second test case, no matter which characters the $2$ occurrences of ? are changed to, the string cannot be made to contain zzz as a contiguous substring.
For the third test case, helloworld itself contains helloworld as a contiguous substring.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。