ABC-076-C Dubious Document 2

■■■問題■■■

E869120は、宝物が入ってそうな箱を見つけました。
しかし、これには鍵がかかっており、鍵を開けるためには英小文字からなる文字列Sが必要です。

彼は文字列S'を見つけ、
これは文字列Sの0個以上 |S| 個以内の文字が?に置き換わった文字列であることも分かりました。
ただし、文字列Aに対して、|A| を「文字列Aの長さ」とします。

そこで、E869120はヒントとなる紙を見つけました。 

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

そのとき、鍵となる文字列Sを出力しなさい。
ただし、そのような文字列Sが存在しない場合は代わりにUNRESTORABLEと出力しなさい。

■■■入力■■■

S'
T

●1 <= |S'|,|T| <= 50
●S'は英小文字と?から成る
●Tは英小文字から成る

■■■出力■■■

鍵となる文字列Sを出力しなさい。
ただし、そのような文字列Sが存在しない場合は、代わりにUNRESTORABLEと出力しなさい。

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "Input1";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("?tc????");
            WillReturn.Add("coder");
            //atcoder
            //条件1を満たす文字列は
            //atcoder, btcoder, ctcoder, ・・・ , ztcoder の26個がありますが、
            //その中で最も辞書順で小さいものは atcoder なので、S=atcoder と特定できます。
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("??p??d??");
            WillReturn.Add("abc");
            //UNRESTORABLE
            //条件1を満たすような文字列Sが存在しないので、
            //鍵となる文字列Sは存在しません。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];
        string T = InputList[1];

        var KouhoList = new List<string>();

        //始点のループ
        for (int I = 0; I <= S.Length - T.Length; I++) {
            bool IsOK = true;
            for (int J = 0; J <= T.Length - 1; J++) {
                if (S[I + J] == '?') continue;
                if (S[I + J] == T[J]) continue;
                IsOK = false;
                break;
            }
            if (IsOK) {
                string WillAdd = S.Remove(I, T.Length);
                WillAdd = WillAdd.Insert(I, T);
                WillAdd = WillAdd.Replace('?', 'a');
                KouhoList.Add(WillAdd);
            }
        }
        if (KouhoList.Count > 0) {
            Console.WriteLine(KouhoList.Min());
        }
        else Console.WriteLine("UNRESTORABLE");
    }
}

解説

置換場所を全部試して、最小文字列が解となります。

一番右側の置換場所のみを試すアルゴリズムだと
S' が ?b?? で
T が ab なケースで
間違った解になってしまいます。