AtCoder Beginner Contest 076 C – Dubious Document 2 をPython3で解く

# AtCoder Beginner Contest 076 C - Dubious Document 2
# https://atcoder.jp/contests/abc076/tasks/abc076_c
# tag: 文字列 書き換え 辞書順 正規表現 E869120

# 自明なこととして、辞書順最小を目指すので、? は可能な限り a に
# 変えるほうがいい。

# しかし、T と一致する部分が最低一箇所は必要。
# 一致箇所が複数ある場合を考える。
# 便宜的に左と右で考えてみると、左側で一致させる場合よりも、
# 右側で一致させるほうが、より左側の ? を a に変更することが
# できる。よって、可能な限り右側で一致させるほうがいい。

# ちなみに公式解説では置き換え可能な全てを求め、
# その中で辞書順最小を出力、としている。
# 制約も緩いので、どちらでもいいかと思う。

def main():
    S = input()
    T = input()

    # T との置換を始める地点を result とする
    result = -1

    # S 上の、|S| - |T| の地点から左に向かって、そこから右の文字列が
    # T と一致 or 置換可能かどうかを探索していく。
    # '(c|?)(o|?)(d|?)...' という感じで組み立てて、正規表現で
    # やってしまう手もあるかもしれないが、やや煩雑かも。
    for start in range(len(S) - len(T), -1, -1):
        for i in range(len(T)):
            # 一文字ずつ一致 or 置換可能かどうかを確認
            if S[start + i] == T[i] or S[start + i] == '?':
                continue
            # 不一致ならスタート地点を左へずらす
            else:
                break

        # 全文字が一致 or 置換可能なら、result を出して break
        else:
            result = start
            break
    
    # result が -1 のままなら、T への置換が不可能
    if result == -1:
        print('UNRESTORABLE')

    # result に値があれば、そこからを T へ置き換え、
    # 他の ? は a に置換して出力
    else:
        S = S.replace('?', 'a')
        print(S[:result] + T + S[result+len(T):])

main()