ABC076 C:Dubious Document 2
苦手な文字列をどうにかしないと…って苦手な分野しかねえわ。
https://atcoder.jp/contests/abc076/tasks/abc076_c
辞書順最小にするということは、できるだけ前方の「?」から「a」にして、後方の「?」を T にマッチさせる用に残しておきたい。 ということで、S と T がマッチしているかどうかをケツから確認していく。その場合、添え字の操作がこんがらがることは目に見えているので、一旦両者とも反転させている。
追記:全部嘘です。
void solve(string s) {
for (auto &c : s) {
if (c == '?') c = 'a';
}
reverse(s.begin(), s.end());
cout << s << endl;
exit(0);
}
signed main() {
string s, t;
cin >> s >> t;
reverse(s.begin(), s.end());
reverse(t.begin(), t.end());
const int s_len = (int)s.size();
const int t_len = (int)t.size();
rep(i, 0, s_len) {
if (s[i] == t[0] || s[i] == '?') {
string sa = s.substr(i, t_len);
if ((int)sa.size() < t_len) continue;
bool ok = true;
rep(j, 0, t_len) {
if (sa[j] != t[j] && sa[j] != '?') {
ok = false;
break;
}
}
if (ok) {
rep(j, 0, t_len) {
s[i++] = t[j];
}
solve(s);
}
}
}
puts("UNRESTORABLE");
}
本当の解法:
https://www.hamayanhamayan.com/entry/2017/10/28/230027