問題概要

英小文字および文字 '?' からなる文字列 $S$ が与えられる。 $S$ の各 '?' を英小文字に置き換えてできる文字列のうち、次の条件を満たす辞書順最小のものを求めよ。

(条件) 文字列 $T$ を連続する部分文字列として含む

制約

$1 \le |S|, |T| \le 50$

考えたこと

制約が小さいので全探索できる！

「 $S$ のどの文字から $T$ と一致するか」を全探索しよう。

もし、 $S$ の $i$ 文字目以降が $T$ と一致する ('?' は $T$ に合わせる) ならば、
残りの '?' はすべて 'a' に置き換える

ようにして得られる文字列が、候補となる。候補となる文字列の中で、最も辞書順が小さいものを答えればよい。

計算量は $O(|S||T|)$ となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    string S, T;
    cin >> S >> T;

    string res = "UNRESTORABLE";
    for (int i = 0; i+T.size() <= S.size(); i++) {
        bool ok = true;
        string tmp = S;
        for (int j = 0; j < T.size(); j++) {
            if (S[i+j] != '?' && S[i+j] != T[j]) ok = false;
            tmp[i+j] = T[j];
        }
        if (ok) {
            for (int j = 0; j < tmp.size(); j++) {
                if (tmp[j] == '?') tmp[j] = 'a';
            }
            if (res == "UNRESTORABLE") res = tmp;
            else res = min(res, tmp);
        }
    }
    cout << res << endl;
}