AtCoder蟻本 初級編 2-2 貪欲法 ③Best Cow Line

ABC071 C - Dubious Document 2(300)

C: Dubious Document 2 - AtCoder Beginner Contest 076 | AtCoder

概要

英小文字からなる文字列と、英小文字と?からなるが与えられる。
はを含み、かつの?を任意の英小文字で置き換えてできる文字列とする。
この時、としてあり得る文字列の中で辞書順最小のものを出力せよ。
ただし、そのような文字列が存在しない場合はUNRESTORABLEと出力せよ。

制約

方針

下記の手順で文字列を作ってゆき、できた文字列をベクトルに格納してゆく。
そのベクトルをソートして辞書順最小の文字を答える。

• の前方からとマッチングして文字列を作ってゆく。マッチングが失敗した場合は次の文字からマッチングを再開する。
• のうちとマッチングしていない部分の?はaに置き換える。

解答

Submission #3887710 - AtCoder Beginner Contest 076 | AtCoder

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	string sd, t;
	cin >> sd >> t;
 
	int n = sd.size();
	int m = t.size();
	if(n < m){
		cout << "UNRESTORABLE" << endl;
		return 0;
	}
 
	vector<string> v;
	for(int i = 0; i+m-1 < n; i++){
		char c[n];
		bool ok = true;
		for(int j = 0; j < n; j++){
			if(j < i || i+m-1 < j){
				c[j] = (sd[j] == '?' ? 'a' : sd[j]);
			}else{
				if(sd[j] == '?' || sd[j] == t[j-i]){
					c[j] = t[j-i];
				}else{
					ok = false;
					break;
				}
			}
		}
		if(ok) {
			string a(c, n);
			v.push_back(a);
		}
	}
 
	if(v.size() == 0){
		cout << "UNRESTORABLE" << endl;
	}else{
		sort(v.begin(), v.end());
		cout << v[0] << endl;
	}
}