問題一覧 > 通常問題

No.2231 Surprising Flash!

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : 👑 AngrySadEightAngrySadEight / テスター : akakimidoriakakimidori
0 ProblemId : 9157 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-18 12:57:06

問題文

はちじくんは,友人の誕生日にプレゼントとして英小文字からなる文字列 $S_1$ を用意して渡すことにしました.

友人を驚かせようと,はちじくんは文字列 $S_1$ を連続する部分列として文字列 $S_2$ を含むように作ろうとしました.しかし,はちじくんは,作ろうとした文字列の一部を忘れてしまいました.

英小文字と,? からなる長さ $N$ の文字列 $S_1$ が与えられ,? ははちじくんがその箇所の文字を忘れたことを表します.はちじくんのために,? を英小文字に置き換えて,連続する部分列として長さ $M$ の文字列 $S_2$ を含む文字列を復元してください.ただし,そのような文字列が複数ある場合には,その中で辞書順最小のものを求め,そのような文字列が無い場合はその旨を報告してください.

$T$ 個のテストケースが与えられるので,それぞれに対して答えを求めてください.

入力

入力は以下の形式で標準入力から与えられる.

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各ケースは以下の形式で与えられる.

$N$ $M$
$S_1$
$S_2$

制約

  • $N, M, T$ は整数である.
  • $1 \leq T \leq 10^5$
  • $1 \leq M \leq N \leq 5 \times 10^5$
  • $S_1$ は英小文字および ? のみからなる長さ $N$ の文字列である.
  • $S_2$ は英小文字のみからなる長さ $M$ の文字列である.
  • 1つの入力ファイルに対し,$N$ の総和は $5 \times 10^5$ を超えない.

出力

$T$ 行にわたって出力せよ.$i(1 \leq i \leq T)$ 行目には $i$ 番目のテストケースについて,$S_1$ のうち ? である箇所を英小文字に変えることで連続する部分列として $S_2$ を含むようにすることが不可能ならば,-1 を出力せよ.可能ならば,そのような文字列の中で辞書順最小のものを出力せよ.

サンプル

サンプル1
入力
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
出力
ghelloworldad
-1
helloworld
tatarakogasa

1つ目のテストケースについて,$2$ 文字目から $11$ 文字目が helloworld となっており,確かに連続する部分列として helloworld を含みます.ほかに ghelloworldld なども連続する部分列として helloworld を含みますが,辞書順最小のものを出力する必要があることに注意してください.

2つ目のテストケースについて,$2$ 個ある ? をどのような文字に変えたとしても,連続する部分列として zzz を含むようにはできません.

3つ目のテストケースについて,helloworld それ自身も,連続する部分列として helloworld を含んでいます.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。