Problem:


Score : 300 points

Problem Statement

E869120 found a chest which is likely to contain treasure.

However, the chest is locked. In order to open it, he needs to enter a string S consisting of lowercase English letters.

He also found a string S', which turns out to be the string S with some of its letters (possibly all or none) replaced with ?.  

One more thing he found is a sheet of paper with the following facts written on it:  

Condition 1: The string S contains a string T as a contiguous substring.

Condition 2: S is the lexicographically smallest string among the ones that satisfy Condition 1.

Print the string S.

If such a string does not exist, print UNRESTORABLE.  

Constraints

1 \leq |S'|, |T| \leq 50

S' consists of lowercase English letters and ?.

T consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T'

Output

Print the string S.

If such a string does not exist, print UNRESTORABLE instead.  

Sample Input 1

?tc????
coder

Sample Output 1

atcoder

There are 26 strings that satisfy Condition 1: atcoder, btcoder, ctcoder,..., ztcoder.
Among them, the lexicographically smallest is atcoder, so we can say S = atcoder.

Sample Input 2

??p??d??
abc

Sample Output 2

UNRESTORABLE

There is no string that satisfies Condition 1, so the string S does not exist.



Sample input:
?tc????
coder


Sample output:
atcoder

Submission status: Accepted

Solution code:
S = input()
T = input()
N = len(S)
M = len(T)



jdg = True

if N < M:
    print("UNRESTORABLE")
else:
    for i in range( N-M+1 ):
        jdg = True
        for j in range(M):
            if S[i+j] != T[j]:
                jdg = False
                break;
        if jdg:
            break;
    

    if jdg:
         ans = S.replace('?', 'a')
         print(ans)

    
    else:
        for i in range( N-M, -1, -1 ):
            jdg = True
            for j in range(M):
                if S[i+j] != T[j] and S[i+j] != '?':
                    jdg = False
                    break;
            if jdg:
                li = list(S)
                li[i:i+M] = T
                S = ''.join(li)
                break;

        if jdg:
            ans = S.replace('?', 'a')
            print(ans)
        else:
            print("UNRESTORABLE")

Submission status: Accepted

Solution code:
Sd_ = input()
T_ = input()
Sd = []
T = []
S = []
for i in range(len(Sd_)):
    Sd.append(Sd_[i])
for i in range(len(T_)):
    T.append(T_[i])


def check(s, t, n):
    for i in range(len(t)):
        if s[n + i] is not t[i] and s[n + i] is not '?':
            return False
    return True


m = len(Sd) - len(T)
while m >= 0:
    if check(Sd[:], T[:], m):
        for j in range(len(T)):
            Sd[m + j] = T[j]
        for a in range(len(Sd)):
            if Sd[a] is '?':
                S.append('a')
            else:
                S.append(Sd[a])
        print(''.join(S))
        exit()
    m -= 1
print('UNRESTORABLE')

Submission status: Accepted

Solution code:
def main():
    Sd = input()
    T = input()

    i1 = [i for i, x in enumerate(Sd) if x == T[0]]
    i2 = [i for i, x in enumerate(Sd) if x == '?']
    indexes = (i1 + i2)[::-1]
    s = list(Sd)
    for i in indexes:
        for j in range(len(T)):
            if i + len(T) <= len(Sd):
                if s[i+j] == T[j] or s[i+j] == '?':
                    s[i+j] = T[j]
                    continue
            s = list(Sd)
            break
        else:
            ans = ''.join(s)
            ans = ans.replace('?', 'a')
            print(ans)
            exit()

    print('UNRESTORABLE')

main()

Submission status: Accepted

Solution code:
def main():
    S_p = input()
    T = input()
    N = len(T)

    str_list = [S_p[i:i+N] for i in range(len(S_p)-N+1)]
    str_candidate = []
    # itemはstr_listの中の一つ
    for i, item in enumerate(str_list):
        # Tとの比較を行い，等しければその部分を使った文字列をcandidateに入れる．
        for j, check_str in enumerate(item):
            if check_str == "?" or check_str == T[j]:
                pass
            else:
                break
            # 次の等式が満たせれば全ての文字が等しかったと判断
            if j+1 == N:
                str_candidate.append(S_p[:i]+T+S_p[i+N:])
    if len(str_candidate) == 0:
        print("UNRESTORABLE")
        return None
    str_result = []
    for item in str_candidate:
        str_result.append(item.replace("?", "a"))
    str_result.sort()
    print(str_result[0])
    return None

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
S = input()
T = input()
ans = []
o = []
def check(S, T):
    for i in range(len(S)):
        if (T[i] == S[i]) or (S[i] == "?"):
            pass
        else:
            return False
    else:
        return True
    
hint_len = len(T)
UnCheck = True
for i in range(len(S)-(hint_len+1) , -2 , -1):
    if check(S[i+1:i+hint_len+1], T):
        Z = list(S)
        Z[i+1:i+hint_len+1] = list(T)
        ans.append(Z)
        UnCheck = False

if UnCheck:
    print("UNRESTORABLE")
    sys.exit()
else:
    for a in ans:
        x = ("".join(a)).replace("?", "a")
        o.append(x)

o.sort()
print(o[0])

Submission status: Accepted

Solution code:
s = input()
t = input()

candidate = ("z" * len(s)) + "a"
for i in range(len(s) - len(t) + 1):
    if s[i] == t[0] or s[i] == '?':
        for j in range(len(t)):
            if s[i + j] != '?' and t[j] != s[i + j]:
                break
        else:
            candidate = min(s[0:i] + t + s[i+len(t):], candidate)
                
if candidate == ("z" * len(s)) + "a":
    print('UNRESTORABLE')
else:
    print(candidate.replace('?', 'a'))

Submission status: Accepted

Solution code:


SD = input()
K = input()

ans_list = []

for i in range(len(SD) - len(K) + 1):
    flag = True
    for j in range(len(K)):
        if SD[i + j] != K[j] and SD[i + j] != '?':
            flag = False
            break
    if flag:
        tmp = SD[:i] + K + SD[len(K) + i:]
        ans_list.append(tmp.replace('?', 'a'))


s_ans_list = sorted(ans_list)
if len(s_ans_list) == 0:
    print('UNRESTORABLE')
else:
    print(s_ans_list[0])

Submission status: Accepted

Solution code:
import sys
s = input()
t = input()
l = len(t)
if t in s:
    print(s.replace('?', 'a'))
    sys.exit()
m = -1
for i in range(len(s) - l + 1):
    f = True
    for j in range(l):
        if s[i:i+l][j] == '?' or s[i:i+l][j] == t[j]:
            pass
        else:
            f = False
    if f:
        m = i
if m < 0:
    print('UNRESTORABLE')
else:
    print((s[0:m] + t + s[m+l:]).replace('?', 'a'))

Submission status: Accepted

Solution code:
s = input()
t = input()

def comp(a, b, n):
	for i in range(n):
		if a[i] != '?' and a[i] != b[i]:
			return False
	return True 

def change(a):
	b = ""
	for i in range(len(a)):
		c = a[i]
		if a[i] == '?':
			c = 'a'
		b += c
	return b

t_len = len(t)
bad = "UNRESTORABLE"

n = len(t)
if len(t) > len(s):
	print(bad)
else:
	found = 0
	for i in range(n, len(s)):
		if comp(s[-i:-(i-n+1)]+s[-(i-n+1)], t, t_len):
			s = change(s)
			if i > n:
				print(s[:-i]+t+s[-(i-n):])
			else:
				print(s[:-i]+t)
			found = 1
			break
	if found == 0:
		if len(s) == len(t):
			if comp(s, t, n):
				print(t)
				found = 1
	if found == 0:
		print(bad)

Submission status: Accepted

Solution code:
import sys,collections
sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

Sp = S()
T = S()
S = ""
flag = True
for i in range(len(Sp)-len(T),-1,-1):
    if flag:
        for j in range(len(T)):
            if Sp[i+j] != "?" and T[j] != Sp[i+j]:
                break
            elif j == len(T)-1:
                S = Sp[0:i] + T + Sp[i+j+1:len(Sp)]
                flag = False
if S == "":
    print("UNRESTORABLE")
else:
    print(S.replace("?", "a"))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys, re, copy, math, itertools
from copy import *
from collections import deque, defaultdict
from heapq import *
from bisect import *
#import numpy as np
#import scipy as sp

# 読み込み
Sp = input()
T  = input()

def exist_match(Sp, T):
    idx = []
    for i in range( len(Sp)-len(T)+1 ):
        OK = 1
        for j in range( len(T) ):
            if Sp[i+j]!='?' and Sp[i+j]!=T[j]:
                OK = 0
                break
        if OK==1:
            idx.append(i)
    return idx

Idx = exist_match(Sp, T)

# マッチなし
if len(Idx)==0:
    print('UNRESTORABLE')
    exit()

# 文字列候補作成
Ls = len(Sp)
Lt = len(T)
Ss = []

for i in Idx:
    S = ""
    for j in range(i) : S += Sp[j]
    for j in range(Lt): S += T[j]
    for j in range(Ls-i-Lt): S += Sp[ i+Lt+j ]
    S = S.replace('?', 'a')
    Ss.append(S)

# 辞書順最小
Ss.sort()
print(Ss[0])

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
flag = False
for i in range(len(s)-len(t)+1) :
    for j in range(len(t)) :
        if s[i+j] != t[j]  and s[i+j] != '?' :
            break
    else :
        flag = True 
        begin = i

if flag :
    ans = ''
    for i in range(len(t)) :
        s[begin+i] = t[i]
    for i in range(len(s)) :
        if s[i] == '?' :
            s[i] = 'a'
        ans += s[i]
    print(ans)
else :
    print('UNRESTORABLE')

Submission status: Accepted

Solution code:
s=input()
t=input()

n=0
a='?'*len(s)
for i in range(len(s)):
    k=0
    for j in range(len(t)):
        if i+j<len(s):
            if s[i+j]==t[j] or s[i+j]=='?':
                k+=1
    if k==len(t):
        n+=1
        a='?' * i + t + '?' * (len(s)-len(t)-i)
b=''

for i in range(len(s)):
    if s[i] != '?':
        b= b+s[i]
    elif a[i] != '?':
        b= b+a[i]
    else:
        b= b+'a'

if n==0:
    print('UNRESTORABLE')
else:
    print(b)

Submission status: Accepted

Solution code:
S1 = input()
T = input()

S1_r = S1[::-1]
T_r = T[::-1]
if len(S1) < len(T):
    print("UNRESTORABLE")
else:    
    for i in range(len(S1)-len(T)+1):
        flag1 = True
        flag2 = True
        for s,t in zip(S1_r[i:i+len(T)],T_r):
            if s == "?" or s == t:
                pass
            else:
                flag1 = False 
                break
        if flag1:
            flag2 = False
            S1_r = S1_r.replace(S1_r[i:i+len(T)],T_r,1)
            S_r = ["a" if s1 == "?" else s1 for s1 in S1_r]
            print("".join(S_r[::-1]))
            break
    if flag2:
        print("UNRESTORABLE")

Submission status: Accepted

Solution code:
S1 = list(input())
T = list(input())
S = S1.copy()
find = False
for i in range(len(S1) - 1, len(T) - 2, -1):
    if S1[i] == T[-1] or S1[i] == '?':
        if len(T) > 1:
            for j in range(1, len(T)):
                if S1[i - j] != '?' and S1[i - j] != T[len(T) - j - 1]:
                    possible = False
                    break
                elif j == len(T) - 1:
                    find = True
        else:
            find = True
        if find:
            S[i - len(T) + 1:i + 1] = T
            break
if find:
    for i in range(len(S)):
        if S[i] == '?':
            S[i] = 'a'
    print(''.join(S))
else:
    print('UNRESTORABLE')

Submission status: Accepted

Solution code:
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np
import copy as cp
S = input()
T = input()
s = len(S)
t = len(T)

rst = []
for i in range(t) : 
    #１文字ずつ検索していく
    #検索範囲は iから(t - i)まで
    flag = False
    for j in reversed(range(i , s + i - t + 1)): 
        if (T[i] != S[j]) & (S[j] != "?") : continue
        else:
            #マッチしたら他の部分もあうか考える
            flag = True
            for k in range(t) : 
                if (T[k] == S[j - i + k]) | (S[j - i + k] == "?"): continue
                else : 
                    flag = False
                    break
            if flag : 
                #これでoKなのでブレイクしてあとはaで埋めます
                x = cp.deepcopy(S)
                for k in range(t) : 
                    if x[j - i + k] == "?" : x = x[ : (j-i+k)] + T[k] + x[(j -i +k + 1) : ]
                x = x.replace("?" , "a")
                rst.append(x)

              
if len(rst) != 0 : 
    
    print(min(rst))
else : 
    print("UNRESTORABLE")

Submission status: Accepted

Solution code:
import re

S2 = input()
T = input()

S_list = []

for j in range(len(S2) - len(T) + 1):
    if S2[j:(j + len(T))] == T:
        S_list.append(re.sub("\?", "a", S2))
    else:
        flag = 1
        tmp_S = ""
        for k in range(len(T)):
            if(S2[j + k] == T[k] or S2[j + k] == "?"):
                pass
            else:
                flag = 0
        if flag == 1:
            tmp = S2[:j] + T + S2[j + len(T):]
            S_list.append(re.sub("\?", "a", tmp))

if S_list == []:
    print("UNRESTORABLE")
else:
    print(sorted(S_list)[0])

Submission status: Accepted

Solution code:
S = input()
T = input()

match_idx = []
for i in range(len(S)):
    is_match = True
    for j in range(len(T)):
        if i + j >= len(S):
            is_match = False
            break
        s = S[i + j]
        t = T[j]
        if not (s == '?' or s == t):
            is_match = False
            break
    if is_match:
        match_idx.append(i)

if len(match_idx) > 0:
    match_idx = match_idx[len(match_idx) - 1]
    ans_S = []
    j = 0
    for i, s in enumerate(S):
        if s == '?':
            if i == match_idx and j < len(T):
                ans_S.append(T[j])
                j += 1
                match_idx += 1
            else:
                ans_S.append('a')
        elif i == match_idx and j < len(T):
            ans_S.append(T[j])
            j += 1
            match_idx += 1
        else:
            ans_S.append(s)
    print(''.join(ans_S))
else:
    print('UNRESTORABLE')

Submission status: Accepted

Solution code:
S_p=raw_input()
T=raw_input()

def match(s,t):
  r=[]
  for i in range(len(s)-len(t)+1):
    c=0
    for j in range(len(t)):
      if s[i+j]==t[j] or s[i+j]=='?':
        c+=1
      if c==len(t):
        r.append(i)

  return r

ps=match(S_p,T)

if len(ps)==0:
  print 'UNRESTORABLE'
else:
  p=ps[-1]
  S_p=S_p.replace('?','a')
  print S_p[0:p]+T+S_p[p+len(T):]

Submission status: Accepted

Solution code:
S = input()
T = input()

start = len(S) - len(T)
end = len(S)

ans = ''
while start >= 0:
	test = S[start:end]
	solve = True
	for i in range(len(T)):
		c1,c2 = test[i],T[i]
		if c1 != c2 and c1 != '?':
			solve = False
			break
	if solve:
		ans = S[:start] + T + S[end:]
		break
	start -= 1
	end -= 1
if len(ans) > 0:
	print(ans.replace('?', 'a'))
else:
	print('UNRESTORABLE')

Submission status: Accepted

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
dp = [[0] * (m + 2) for _ in range(n + 2)]
s = " " + s
t = " " + t
for i in range(n + 1):
    dp[i][0] = 1
flag = False
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i] == t[j] or s[i] == '?':
            dp[i][j] = dp[i - 1][j - 1]
    if dp[i][m]:
        flag = True
if not flag:
    print("UNRESTORABLE")
else:
    i = n
    res = str()
    while not dp[i][m]:
        res = ('a' if s[i] == '?' else s[i]) + res
        i -= 1
    while m:
        res = t[m] + res
        i -= 1
        m -= 1
    while i:
        res = ('a' if s[i] == '?' else s[i]) + res
        i -= 1
    print(res)

Submission status: Accepted

Solution code:
s = input()
t = input()
flag = []
for i in range(0, len(s)-len(t)+1):
    num = 0
    while True:
        if num == len(t):
            flag.append(i)
            break
        elif s[i + num] not in [t[num], '?']:
            break
        else:
            num += 1
if not flag:
    print ('UNRESTORABLE')
else:
    answers = []
    for ind in flag:
        ans = s[:ind] + t + s[ind+len(t):]
        if '?' in ans:
            ans = ans.replace('?', 'a')
        answers.append(ans)
    answers.sort()
    print (answers[0])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

"""076-c"""


import sys

def kmp(T, P):
    n, m = len(T), len(P)
    j = 0
    k = 0
    fail = kmp_fail(P)
    while j < n:
        if T[j] == P[k] or T[j] == '?':
            if k == m - 1:
                return j - m + 1
            j += 1
            k += 1
        elif k > 0:
            k = fail[k-1]
        else:
            j += 1
    return -1

def kmp_fail(P):
    n = len(P)
    fail = [0] * n
    j = 1
    k = 0
    while j < n:
        if P[j] == P[k]:
            fail[j] = k + 1
            j += 1
            k += 1
        elif k > 0:
            k = fail[k - 1]
        else:
            j += 1
    return fail


def main():
    """Main function."""
    S_p = input()
    T = input()

    pos = kmp(S_p, T)

    if pos < 0:
        print('UNRESTORABLE')
        sys.exit(0)

    total = pos

    pos_ = 0
    while pos_ >= 0:
        pos_ = kmp(S_p[pos+1:], T)
        if pos_ >= 0:
            pos = pos + pos_ + 1

    S_cand = S_p[:pos] + T + S_p[pos+len(T):]

    S = S_cand.replace('?', 'a')
    print(S)

if __name__ == '__main__':
    sys.exit(main())

Submission status: Accepted

Solution code:
# coding: utf-8
S = list(raw_input())
T = list(raw_input())

idx = []
for i in range(len(S)):
    match = 0
    for j in range(len(T)):
        if i+len(T) > len(S):
            break
        if S[i+j] == T[j] or S[i+j] == '?':
            match += 1
    if match == len(T):
        idx.append(i)

if len(idx) == 0:
    print 'UNRESTORABLE'
else:
    i = max(idx)
    for j in range(len(T)):
        S[i+j] = T[j]
    prev_idx = i

    # fill a
    for i in range(len(S)):
        if S[i] == '?':
            S[i] = 'a'

    print ''.join(S)

Submission status: Accepted

Solution code:
import sys

def match(a, b):
    for i in range(len(a)):
        if a[i] != '?' and b[i] != '?' and a[i] != b[i]:
            return False
    return True


Y=str(input())
T=str(input())
S = ''
if len(Y) < len(T):
    print('UNRESTORABLE')
    sys.exit()

if match(T,Y[-len(T):]):
    S = Y[:-len(T)] + T
    A = S.replace('?','a')
    print(A)
    sys.exit()
else:
    for i in range(len(Y) - len(T)):
        i += 1
        k = -(len(T)+i)
        if match(T, Y[k:-i]):
            S = Y[:k] + T + Y[-i:]
            A = S.replace('?','a')
            print(A)
            sys.exit()

print('UNRESTORABLE')

Submission status: Accepted

Solution code:
Sd = list(input())
T = list(input())

find = False
for i in range(len(Sd) - len(T) + 1)[::-1]:
    flag = True
    for j in range(len(T)):
        if Sd[i + j] != '?' and Sd[i + j] != T[j]:
            flag = False
            break
    if flag:
        find = True
        for j in range(len(T)):
            Sd[i + j] = T[j]
        break

if find:
    for i in range(len(Sd)):
        if Sd[i] == '?':
            print('a', end='')
        else:
            print(Sd[i], end='')
    print()
else:
    print('UNRESTORABLE')

Submission status: Accepted

Solution code:
def main():
    s = raw_input().strip()
    t = raw_input().strip()

    ans = []

    def normal():
        m = '?' * len(t)
        pos = s.rfind(m)
        if pos == -1:
            return 
        
        mod = s[:pos] + t + s[pos + len(t): ]
        mod = mod.replace('?', 'a')
        ans.append(mod)

    def solve(pos):

        for i in xrange(len(s)):
            if s[i] == t[pos]:
                ss = (i - pos)
                ee = i + (len(t) - 1 - pos)
                if ss < 0 or ee >= len(s): 
                    continue

                tmp = s[ss: ee+1]
                ok = True
                for j in xrange(len(tmp)):
                    if tmp[j] == '?': 
                        continue 
                    if tmp[j] != t[j]: 
                        ok = False
                        break
                if ok:
                    mod = s[:ss] + t + s[ee+1: ]
                    mod = mod.replace('?', 'a')
                    ans.append(mod)

    for i in xrange(len(t)):
        solve(i)

    normal()
    if ans:
        return min(ans)
    return "UNRESTORABLE"

print main()

Submission status: Accepted

Solution code:
s,t=list(input()),list(input())
for i in reversed(range(len(s)-len(t)+1)):
	flag=1
	for j in range(i,i+len(t)):
		if s[j]!='?' and s[j]!=t[j-i]:
			flag=0
			break
	if flag:
		ans=""
		for j in range(len(s)):
			if j in range(i,i+len(t)):
				ans+=t[j-i]
			elif s[j]=='?':
				ans+="a"
			else:
				ans+=s[j]
		print(ans)
		break
else:
	print("UNRESTORABLE")

Submission status: Accepted

Solution code:
import copy
s = input()
t = input()
ls = list(s)
lt = list(t)
done = 0
for a in range(len(t)):
    # if(done):
    #     break
    for b in range(len(s)):
        ls = list(s)
        lt = list(t)
        # if(done):
        #     break
        find = 1
        if ls[b] == lt[a] or ls[b] == '?':
            if b >= a and b + (len(t) - (a+1)) <= len(s) - 1:
                for c in range(len(t)):
                    if lt[c] == ls[b-a+c] or ls[b-a+c] == '?':
                        # print("good:",b-a+c,c,ls[b-a+c],lt[c]," | ",b,a,find)
                        pass
                    else:
                        # print("bad:",b-a+c,c,ls[b-a+c],lt[c]," | ",b,a,find)
                        find = 0
                        break
                if(find):
                    ans = copy.deepcopy(ls)
                    for d in range(len(t)):
                        ans[b-a+d] = lt[d]
                    done = 1
                    # break
if done:
    for e in range(len(s)):
        if ans[e] == '?':
            ans[e] = 'a'
    print("".join(ans))
else:
    print("UNRESTORABLE")

Submission status: Accepted

Solution code:
s = list(input())
t = list(input())
ans = []
ok = -1
f = -1
if len(s)<len(t):
    print('UNRESTORABLE')
    exit()

for i in range(len(s)-len(t)+1):
    # print(s[i])
    a = 0
    if s[i] == '?' or s[i] == t[0]:
        if f is -1:
            f=i
        for j in range(len(t)):
            # print(i,j,s[i+j],t[j])
            if s[i+j] != '?' and s[i+j] != t[j]:
                break
            a = j
        if a == len(t)-1:
            ok = i
if ok == -1:
    print('UNRESTORABLE')
    exit()
else:
    for i in range(len(s)):
        if s[i] == '?':
            s[i] = 'a'
        if  ok<= i <= ok+len(t)-1:
            s[i] = t[i-ok]

print(''.join(s))

Submission status: Accepted

Solution code:
def filla(s):
    sret=""
    for i in range(len(s)):
        if s[i] == '?':
            sret += 'a'
        else:
            sret += s[i]
    return sret

s=input()
t=input()

scand=s
bl=True

for i in range(len(s)):
    if len(s) - len(t) >= i:
        for j in range(len(t)):
            if s[i+j] != t[j] and s[i+j] != '?':
                break
            if j == len(t)-1:
                bl=False
                scand = s
                for k in range(len(t)):
                    str_list=list(scand)
                    str_list[i+k]=t[k]
                    scand="".join(str_list)

if bl:
    print("UNRESTORABLE")
else:
    print(filla(scand))

Submission status: Accepted

Solution code:
S = input()
T = input()
result = "UNRESTORABLE"
b = True
for i in range(len(S) - len(T) + 1):
    for j in range(len(T)):
        if S[i + j] != T[j] and S[i + j] != "?":
            break
        if j == len(T) - 1:
            s = (S[:i] + T + S[i + len(T):]).replace("?", "a")
            if b or s < result:
                result = s
                b = False
print(result)

Submission status: Accepted

Solution code:
Sd = input()
T = input()

def check(A, B):
    for a, b in zip(A, B):
        if a != '?' and a != b:
            return False

    return True


for i in range(len(Sd) - len(T) + 1)[::-1]:
    if check(Sd[i:i + len(T)], T):
        print((Sd[:i] + T + Sd[i + len(T):]).replace('?', 'a'))
        break
else:
    print('UNRESTORABLE')

Submission status: Accepted

Solution code:
import re
def main():
    u = 'UNRESTORABLE'
    S = input()
    T = input()

    n = len(T)
    if len(S)-len(T) < 0:
        print(u)
        return

    for n in range(len(S)):
        s = len(S) - len(T) - n
        if s < 0:
            break
        e = s + len(T)
        U = S[s:e]
        if re.search(U.replace("?","."), T):
            S = S[:s] + T + S[e:]
            S = S.replace("?","a")
            print(S)
            return

    print(u)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/python

import re
import sys

def main(argv):
    line = sys.stdin.readline()
    while line:
        S = line.rstrip("\n")
        T = sys.stdin.readline().rstrip("\n")

        pattern = "(.*)("
        for t in T:
            pattern = "{0}(?:{1}|\?)".format(pattern, t)
        pattern = "{0}(.*))".format(pattern)
        regex = re.compile(pattern)
        match = regex.search(S)
        if match:
            print("{0}{1}{2}".format(match.group(1), T, match.group(3)).replace("?", "a"))
        else:
            print("UNRESTORABLE")

        line = sys.stdin.readline()

if __name__ == "__main__":
    main(sys.argv)

Submission status: Accepted

Solution code:
S_ = input()
T = input()
loop = len(S_) - len(T) + 1
stringlist = []

# check S_ in T
for n in range(loop):
    chance = True
    for i in range(len(T)):
        if S_[n+i] == T[i] or S_[n+i] == "?":
            pass
        else:
            chance = False
            break

    if chance:
        tmp = S_[:n] + T + S_[n+len(T):]
        stringlist.append(tmp)

if len(stringlist) == 0:
    print("UNRESTORABLE")
else:
    stringlist.sort()
    String = stringlist[0]
    S = ""
    for i in range(len(S_)):
        if String[i] == "?":
            S += "a"
        else:
            S += String[i]
    print(S)

Submission status: Accepted

Solution code:
import re


def solve(s, t):
    s = s.replace('?', '.')
    ls, lt = len(s), len(t)
    if ls < lt:
        return 'UNRESTORABLE'
    ans = []
    for i in range(ls - lt + 1):
        m = re.match(s[i:i + lt], t)
        if m is None:
            continue
        ans.append((s[:i] + t + s[i + lt:]).replace('.', 'a'))
    if not ans:
        return 'UNRESTORABLE'
    return min(ans)


s = input().strip()
t = input().strip()

print(solve(s, t))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc076.contest.atcoder.jp/tasks/abc076_c
WA
"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    S = input().strip()
    T = input().strip()

    s_len = len(S)
    t_len = len(T)
    gap = s_len - t_len

    ans = 'UNRESTORABLE'
    while gap >= 0:
        matched = True
        for i in range(t_len):
            if S[gap + i] != T[i] and S[gap + i] != '?':
                matched = False
                break
        if matched is True:
            ans = S[:gap] + T + S[gap+t_len:]
            ans = ans.replace('?', 'a')
            break
        gap -= 1

    print(ans)



if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
s0 = (input())
t = (input())

flag = False

ans = ""
lt = len(t)
for i in range(len(s0)-len(t) + 1):

#	print (i)
#	print (s0[i:i+lt])

	flag2= True
	for j in range(lt):
		if s0[i+j] != t[j] and s0[i+j] != "?":
			flag2 = False
			break
	if flag2:
		flag = True
		temp = s0[:i] + t + s0[i+lt:]
		temp = temp.replace('?', 'a')
		if ans == "" or temp < ans:
			ans = temp

if(flag == False):
	print ("UNRESTORABLE")
else:
	print (ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(s, t):
    cands = set()
    t0_idx_max = len(s) - len(t)
    for t0_idx in range(t0_idx_max + 1):
        if all(s[i + t0_idx] in (t[i], "?") for i in range(len(t))):
            cand_chars = list(s)
            for i in range(len(t)):
                cand_chars[i + t0_idx] = t[i]
            for i in range(len(cand_chars)):
                if cand_chars[i] == "?":
                    cand_chars[i] = "a"
            cand = "".join(cand_chars)
            cands.add(cand)
    return min(cands, default=None)


def main():
    s = input()
    t = input()
    res = solve(s, t)
    print("UNRESTORABLE" if res is None else res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
S,T = input(),input()
N,M = len(S),len(T)

found = []
for i in range(N-M+1):
    for j in range(M):
        c1 = S[i+j]
        c2 = T[j]
        if c1 != '?' and c1 != c2: break
    else:
        found.append(i)

if len(found) == 0:
    print('UNRESTORABLE')
    sys.exit()

ans = []
for i in range(N):
    if found[-1] <= i < found[-1] + M:
        ans.append(T[i - found[-1]])
    elif S[i] == '?':
        ans.append('a')
    else:
        ans.append(S[i])
print(''.join(ans))

Submission status: Accepted

Solution code:
s = input()
t = input()
n = len(s)
m = len(t)
start = -1
for i in range(n-m+1):
  success=True
  #print(i)
  for j in range(m):
    #print(s[j+i],t[j])
    if s[j+i] != t[j] and s[j+i] != '?':
      success=False
      break

  if success:
    start=i
res = ''
if start < 0:
  print("UNRESTORABLE")
  exit(0)
for i in range(start):
  if s[i]=='?':
    res += 'a'
  else:
    res += s[i]
for i in range(start,start+m):
  res += t[i-start]
for i in range(start+m,n):
  if s[i]=='?':
    res += 'a'
  else:
    res += s[i]
print(res)

Submission status: Accepted

Solution code:
sd = list(input())
t  = list(input())

change_list = []

for i in range(len(sd)-len(t)+1):
    cut = sd[i:i+len(t)]
    for j in range(len(cut)):
        if cut[j]==t[j]:
            continue
        elif cut[j]=="?":
            cut[j] = t[j]
        else:
            break
    if cut == t:
        change_s = sd[:i] + cut + sd[i+len(t):]
        change_list.append(change_s)
    
if len(change_list)>0:
    change_list = ["".join(x) for x in change_list ]
    change_list = [x.replace("?","a") for x in change_list]
    change_list.sort()
    print(change_list[0])
else:
    print("UNRESTORABLE")

Submission status: Accepted

Solution code:
# encoding:utf-8

def main():
	s = list(input())
	t = list(input())
	print(checker(s, t))

def checker(s, t):
	for i in range(len(s)):
		if i >= len(t) - 1:
			if checker2(s, t, len(s) - i - 1):
				for i2 in range(len(t)):
					s[len(s) - i  - 1 + i2] = t[i2]
				for i2 in range(len(s)):
					if s[i2] == "?":
						s[i2] = "a"
				return "".join(s)

	return "UNRESTORABLE"


def checker2(s, t, i):
	for i2 in range(len(t)):
		#print(i, i2)
		#print(s[i + i2], t[i2])
		if s[i + i2] == "?":
			continue
		elif s[i + i2] == t[i2]:
			continue
		else:
			return False

	return True



if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
S_prime = input()
T = input()

S_prime_r = list(S_prime[::-1])
T_r = list(T[::-1])

for i in range(len(S_prime)-len(T)+1):
    for j in range(len(T)):
        if T_r[j] != S_prime_r[i+j] and S_prime_r[i+j] != "?":
            break
    else:
        for j in range(len(T)):
            S_prime_r[i+j] = T_r[j]
        for k in range(len(S_prime)):
            if S_prime_r[k] == "?":
                S_prime_r[k] = "a"
        print("".join(S_prime_r[::-1]))
        break
        
else:
    print("UNRESTORABLE")

Submission status: Accepted

Solution code:
S = raw_input()
T = raw_input()

LS = len(S)
LT = len(T)

if LS < LT:
  print 'UNRESTORABLE'
  exit()

answers = []
SA = S.replace('?', 'a')
for i in xrange(LS - LT + 1):
  # T start at S[i]
  for j in xrange(LT):
    if S[i+j] != '?' and S[i+j] != T[j]:
      break
  else:
    answers.append(SA[:i] + T + SA[i+LT:])

if len(answers) == 0:
  print 'UNRESTORABLE'
  exit()

print sorted(answers)[0]