Edited at

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 に追加する。

全て探索した後、vectorsort し、最初の文字列が答えである。


  • 文字列の大きさが変化しない(=インデックスをはみ出さない)

  • $?$ ではない英小文字が変化しない

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;
}