ABC76 C-Dubious Document2 - acchan’s blog

問題概要

宝物が入っていそうな箱を開けたいが鍵がかかっている。
この箱には鍵がかかっていて、開けるためには、英小文字からなる文字列Sが必要
鍵となりうる文字列S'を見つけ、これは、文字列Sの0個以上|S|個いないの文字が'?'に置き換わった文字列である。
鍵を解くためのヒントが書かれた紙には次の2つのことが書かれていた。
- 文字列Sの中に連続する部分文字列として英小文字からなる文字列Tが含まれている。
- Sは、上の条件を満たす文字列の中で辞書順最小の文字列この時、鍵となる文字列Sを出力せよ。ただし、そのような文字列Sが存在しない場合は、'UNRESTORABLE'と出力せよ。

制約

1 ≤ |S'|, |T| ≤ 50
S'は英小文字と?からなる
Tは英小文字からなる

考えたこと

Tとマッチするような文字列をおける可能性のあるのはSの頭から数えて何文字目か(これをkとする)を求める。
これが見つからない場合は、UNRESTORABLEを出力
見つかった場合は、s[k+i] = t[i]を埋めたのち、残りの?を辞書順最小を満たすためにaで埋める

#include<bits/stdc++.h>
using namespace std;
string s, t;

bool match(int k) {
  for(int i = 0; i < t.length(); ++i) {
    if(t[i] != s[i+k] && s[i+k] != '?') return false;
  }
  return true;
}

string construct(int k) {
  string ans = s;
  for(int i = 0; i < t.length(); ++i) {
    ans[k+i] = t[i];
  }
  for(int i = 0; i < s.length(); ++i) {
    if(ans[i] == '?') ans[i] = 'a';
  }
  return ans;
}

int main() {
  cin >> s >> t;
  int k = -1; // マッチする文字列が見つからなかったために-1で初期化
  string ans;
  for(int i = 0; i < s.length() - t.length() + 1; ++i) {
    if(match(i)) k = i;
  }
  if(k==-1) {
    cout << "UNRESTORABLE" << endl;
  } else {
    ans = construct(k);
    cout << ans << endl;
  }
  return 0;