AtCoder ABC076 C - Dubious Document 2 (300点)

問題概要

問題のリンク

文字列$S$の $0$ 個以上 $|S|$ 個以下の文字が $?$ に変わった文字列 $S′$ がある。

以下の条件が与えられる。

• 条件1：文字列 $S$ の中に連続する部分文字列として英小文字から成る文字列 $T$ が含まれている。
• 条件2： $S$ は、条件1を満たす文字列の中で辞書順最小の文字列である。

文字列 $S$ を出力せよ。
ただし文字列 $S$ が存在しない時は $UNRESTORABLE$ と出力せよ。

制約条件

• $1≤|S′|,|T|≤50$
• $S′$ は英小文字と ? から成る
• $T$ は英小文字から成る

考えたこと

条件2より、 $S'$ の $?$ の部分は $a$ が入ることが望ましい。よって $?$でない部分を与えられた部分文字列 $T$ と比較していく。

文字列 $S′$ に部分文字列$T$を代入しても、以下の条件を満たすのであれば vector に追加する。
全て探索した後、vector を sort し、最初の文字列が答えである。

• 文字列の大きさが変化しない（=インデックスをはみ出さない）
• $?$ ではない英小文字が変化しない

vector が空であれば $UNRESTORABLE$ と出力する。
計算量は $O(|S′||T|)$ である。

解答

c.cpp

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

int main() {
    string s,t; cin >> s >> t;
    vector<string> ans;
    int l = s.size()-t.size()+1;
    for(int i = 0; i < max(0, l); i ++) {
        string tmp = s;
        for(int j = 0; j < t.length(); j ++) {
            if(i+j>s.size()-1) break;
            if(tmp[i+j]=='?' || tmp[i+j]==t[j]) tmp[i+j] = t[j];
            else break;
            if(j==t.length()-1) {
                for(int k = 0; k < tmp.length(); k ++) {
                    if(tmp[k]=='?') tmp[k] = 'a';
                }
                ans.push_back(tmp);
            }
        }
    }
    sort(ans.begin(), ans.end());
    cout << (ans.size() > 0 ? ans[0] : "UNRESTORABLE") << endl;
    return 0;
}