[ABC076C] Dubious Document 2
题意翻译
你找到了一个装着宝物的箱子,但箱子被锁住了,密码是一个字符串 $S$ 。
但是你手中的密码字符串 $S'$ 是不完整的,残缺的部分用 `?` 替代。你还找到一张纸条,上面有一个串 $T$ 。
已知 $T$ 为 $S$ 的子串。你需要破解这个密码,请输出密码所有可能中字典序最小的代码。如果没有符合的密码,请输出一个字符串 `UNRESTORABLE` 。
$S,S',T$ 的长度均小于 50 ,所有字符均为小写字母或 `?` 。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc076/tasks/abc076_c
E869120 は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列 $ S $ が必要です。
彼は文字列 $ S' $ を見つけ、これは文字列 $ S $ の $ 0 $ 個以上 $ |S| $ 個以内の文字が `?` に置き換わった文字列であることも分かりました。
ただし、文字列 $ A $ に対して、$ |A| $ を「文字列 $ A $ の長さ」とします。
そこで、E869120 はヒントとなる紙を見つけました。
- 条件1:文字列 $ S $ の中に連続する部分文字列として英小文字から成る文字列 $ T $ が含まれている。
- 条件2:$ S $ は、条件1を満たす文字列の中で辞書順最小の文字列である。
そのとき、鍵となる文字列 $ S $ を出力しなさい。
ただし、そのような文字列 $ S $ が存在しない場合は代わりに `UNRESTORABLE` と出力しなさい。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ S' $ $ T $
输出格式
鍵となる文字列 $ S $ を出力しなさい。
ただし、そのような文字列 $ S $ が存在しない場合は、代わりに `UNRESTORABLE` と出力しなさい。
输入输出样例
输入样例 #1
?tc????
coder
输出样例 #1
atcoder
输入样例 #2
??p??d??
abc
输出样例 #2
UNRESTORABLE
说明
### 制約
- $ 1\ \leq\ |S'|,\ |T|\ \leq\ 50 $
- $ S' $ は英小文字と `?` から成る
- $ T $ は英小文字から成る
### Sample Explanation 1
条件1 を満たす文字列は `atcoder`, `btcoder`, `ctcoder`,..., `ztcoder` の $ 26 $ 個がありますが、その中で最も辞書順で小さいものは `atcoder` なので、$ S\ = $`atcoder` と特定できます。
### Sample Explanation 2
条件1を満たすような文字列 $ S $ が存在しないので、鍵となる文字列 $ S $ は存在しません。