# 問題

https://atcoder.jp/contests/abc076/tasks/abc076_c

部分的に隠されている文字列 $S$ とその一部である可能性のある文字列 $T$ ２つの文字列から元の文字列を復元する問題です.
文字列 $T$ を含めた後の文字列 $S$ の辞書順最小の文字列が答えです.

辞書順最小とは辞書で使われているような、先頭からa→zの順に並べて先頭に来るものです.

aaa <-- 辞書順最小
aba
baa
bba

# 入力

S
T

S - 英小文字と'?'により構成された長さ1以上50以下の文字列
T - 英小文字のみで構成された長さ1以上50以下の文字列

# 出力

S1

復元出来る場合は復元後の文字列を、復元不可能な場合はUNRESTORABLEと出力します.

# 入出力例

?tc????
coder

atcoder

まず隠された文字列 $S$ に $T$ を当てはめます.
?tcoderとなります.
そして先頭の?はaからzまで可能性がありますが、辞書順最小が答えなのでaが答えになります.

# 解説

まずは $T$ を $S$ のどこに当てはめるかを決めます.
$S$ に含まれる?はワイルドカード（どんな文字ともイコール）として、 $S$ の部分文字列の中で $T$ と一致する文字列が存在するかをチェックすれば良いです.
この時この独自のイコールの定義を関数としてまとめておくとコードの見通しが良くなります.
１つも見つからなければ答えはUNRESTORABLEとなります.
１つだけ見つかった場合はそこに $T$ を埋め込んで残りの?をすべてaに置き換えれば答えになります.

問題になるのは２箇所以上 $T$ を埋め込める位置が見つかった場合です.
例えば以下のような入力であれば多数の可能性があります.

a???????????????????????????????a
coder

この時辞書順最小という制約に着目すると、 $T$ は常に一番最後に見つかった位置に埋め込むべきであることが分かります.
なぜなら $T$ と同じ長さをもつaのみの文字列であれば常にaのみの文字列の方が辞書順で早いか等しいからです.

aaaaa < coder
aaaaa = aaaaa

最後の位置を見つけるには先頭から検索する代わりに末尾から検索して最初に見つかったものを返せば良いです.
標準ライブラリによくある実装ではrfindという関数名になっています.

# 計算量

２つの文字列の長さをそれぞれ $S$ , $T$ とすると、計算量ステップ数は

(S - T) \times T

となります.
$S = 50, T = 25$ の時最大となり計算量ステップ数は $625$ 程度です.

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

bool equal(string a, string b) {
  loop(n,0,a.size()) {
    if (a[n] == '?') continue;
    if (a[n] != b[n]) return false;
  }
  return true;
}

Int rfind(string &a, string &b) {
  loopdown(n,a.size()-b.size(), -1) {
    if (equal(a.substr(n, b.size()), b)) return n;
  }
  return -1;
}

string S, T;

void input() {
  cin >> S >> T;
}

void solve() {
  auto index = rfind(S, T);
  if (index < 0) {
    cout << "UNRESTORABLE" << endl;
    return;
  }

  loop(n,0,S.size()) {
    if (index <= n && n < (index+T.size())) cout << T[n-index];
    else if (S[n] == '?') cout << 'a';
    else cout << S[n];
  }
  cout << endl;
  return;
}

int main() {
  input();
  solve();
  return 0;
}

ABC076 C - Dubious Document 2