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: Wrong Answer

Solution code:
#http://abc076.contest.atcoder.jp/
# -*- coding: utf-8 -*-
from collections import Counter
from os import sys

s = list(input())
t = input()

def error():
    print('UNRESTORABLE')
    sys.exit()


hatena_count = Counter(s)['?']
if hatena_count < len(t): error()

kouho = []
for i,char in enumerate(s):
    if char == t[0] or char == '?':
        result = True
        for j,t_char in enumerate(t):
            try:
                jouken = t_char == s[i+j] or s[i+j] == '?'
                if not jouken:
                    result = False
                    break
            except IndexError:
                result = False
                break

        if result == True:
            kouho.append(i)

if len(kouho) == 0: error()


kouho = max(kouho)
for i in range(len(t)):
    s[kouho+i] = t[i]

for i,char in enumerate(s[:]):
    if char == '?':
        s[i] = 'a'

result = ''
for char in s:
    result += char

print(result)

Submission status: Wrong Answer

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

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)
for i in range(len(S)-(hint_len+1) , -1 , -1):
    if check(S[i+1:i+hint_len+1], T):
        S = list(S)
        S[i:i+hint_len+1] = list(T)
        for i in range(len(S)):
            if S[i] == "?":
                S[i] = "a"
        print("".join(S))
        break

else:
    print("UNRESTORABLE")

Submission status: Wrong Answer

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

S = list(S)
T = list(T)
s_l, t_l = len(S), len(T)
not_find = False
start_i = 0
for i in range(s_l - t_l + 1):
    start_i = s_l - i - t_l
    here = True
    for j in range(t_l):
        if S[start_i+j] == T[j] or S[start_i+j] == '?':
            here = True
        else:
            here = False
            break
    if here:
        break
    if start_i == 0:
        not_find = True

if not_find:
    print("UNRESTORABLE")
else:
    for s in range(len(S[:start_i])):
        if S[s] == '?':
            S[s] = 'a'

    S[start_i:start_i+t_l] = T

    for s in range(len(S[start_i+t_l:])):
        if S[s] == '?':
            S[s] = 'a'
    print(S)

Submission status: Wrong Answer

Solution code:


SD = input()
K = input()

if K in SD:
    ANS = SD.replace('?', 'a')
    print(ANS)
else:
    RSD = SD[::-1]
    RK = K[::-1]

    length = len(RK)
    flag = False
    j = 0
    for i in range(len(RSD)):
        if RK[j] == RSD[i] or RSD[i] == '?':
            j += 1
            if length == j:
                rem = i
                flag = True
                break
        else:
            j = 0

    if flag:
        j = len(RK) - 1
        list_RSD = list(RSD)
        list_RK = list(RK)
        for i in range(rem, rem - length, -1):
            list_RSD[i] = list_RK[j]
            j -= 1
        RSD = "".join(list_RSD)
        ANS = RSD[::-1]
        ANS = ANS.replace('?', 'a')
        print(ANS)
    else:
        print('UNRESTORABLE')

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

    print('UNRESTORABLE')

main()

Submission status: Wrong Answer

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 = ""
for i in range(len(Sp)-len(T),-1,-1):
    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:len(Sp)-1]
if S == "":
    print("UNRESTORABLE")
else:
    print(S.replace("?", "a"))

Submission status: Wrong Answer

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:
    # fill T
    prev_idx = len(S)
    for i in sorted(idx, reverse=True):
        if i + len(T) > prev_idx:
            continue
        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: Wrong Answer

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 = 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: Wrong Answer

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

for x in t:
    if x in s:
        idx = s.index(x)
        res = "".join(s[:idx] + list(t) + s[idx+len(t):])
        res = res.replace("?", "a")
        if len(res) != len(s):
            print("UNRESTORABLE")
            break
        print(res)
        break
else:
    print("UNRESTORABLE")

Submission status: Wrong Answer

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

a = None
for i,s in enumerate(S_):
    if s == '?': continue
    if T.find(s) != -1 and len(S_[i:]) >= len(T):
        b = set(S_[i:i+len(T)]) - set(['?']) 
        c = set(T)
        if len(b-c) == 0:
            a = i
if a == None:
    print('UNRESTORABLE')
else:
    S_ = S_[:a] + T + S_[i+len(T):]
    print(S_.replace('?','a'))

Submission status: Wrong Answer

Solution code:
#http://abc076.contest.atcoder.jp/
# -*- coding: utf-8 -*-
from collections import Counter
from os import sys

s = list(input())
t = input()

def error():
    print('UNRESTORABLE')
    sys.exit()


hatena_count = Counter(s)['?']
if hatena_count < len(t):
    error()

kouho = []
for i,char in enumerate(s):
    if char == t[0]:
        result = True
        for j,t_char in enumerate(t):
            try:
                if t_char != s[i+j] and s[i+j] != '?':
                    result = False
                    break
            except IndexError:
                error()

        if result == True:
            kouho.append(i)

if len(kouho) == 0: error()

kouho = max(kouho)
for i in range(len(t)):
    s[kouho+i] = t[i]

for i,char in enumerate(s[:]):
    if char == '?':
        s[i] = 'a'

result = ''
for char in s:
    result += char

print(result)

Submission status: Wrong Answer

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)):
        print("%d, %d" % (i, j))
        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: Wrong Answer

Solution code:


SD = input()
K = input()

RSD = SD[::-1]
RK = K[::-1]

length = len(RK)
flag = False
j = 0
for i in range(len(RSD)):
    if RK[j] == RSD[i] or RSD[i] == '?':
        j += 1
        if length == j:
            rem = i
            flag = True
            break
    else:
        j = 0

if flag:
    j = len(RK) - 1
    list_RSD = list(RSD)
    list_RK = list(RK)
    for i in range(rem, rem - length, -1):
        list_RSD[i] = list_RK[j]
        j -= 1
    RSD = "".join(list_RSD)
    ANS = RSD[::-1]
    ANS = ANS.replace('?', 'a')
    print(ANS)
else:
    print('UNRESTORABLE')

Submission status: Wrong Answer

Solution code:
s = list(input())
t = list(input())
ans = []
ok = -1
f = -1
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 ok == -1 and 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: Wrong Answer

Solution code:
s = list(input())
t = list(input())
ans = []
ok = -1
f = -1
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 ok == -1 and 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(s)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-       

s = input()
t = input()
ansstr = []

flg = True
for i in range(len(s)-len(t)+1)[::-1]:
    tmpstr = s[i:i+len(t)]
    flg = True
    for j in range(len(t)):
        if(tmpstr[j] == '?'):
            pass
        elif(tmpstr[j] == t[j]):
            pass
        else:
            flg = False
    if(flg):
        for k in range(len(s)):
            if(i<=k and k<i+len(t)):
                ansstr += t[k-i]
            elif(s[k]=='?'):
                ansstr += 'a'
            else:
                ansstr += s[k]
        break
print(''.join(ansstr) if flg else 'UNRESTORABLE')

Submission status: Wrong Answer

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

find = False
for i in range(len(Sd) - len(T) + 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: Wrong Answer

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 + ls], 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: Wrong Answer

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

for i, x in enumerate(t):
    if x in s:
        idx = s.index(x)
        res = "".join(s[:idx] + list(t) + s[idx+len(t):])
        res = res.replace("?", "a")
        print(res)
        break
else:
    print("UNRESTORABLE")

Submission status: Wrong Answer

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

def match(s,t):
  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):
        return i

  return -1

p=match(S_p,T)

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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
http://abc076.contest.atcoder.jp/tasks/abc076_c

"""
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

    matched = True
    ans = 'UNRESTORABLE'
    while gap >= 0:
        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: Wrong Answer

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

idx = SS.find(T[0])
if idx == -1:
  print("UNRESTORABLE")
  exit()

SS = list(SS)
T = list(T)
SS[idx:idx+len(T)] = T
SS = ("".join(SS)).replace("?", "a")
print(SS)

Submission status: Wrong Answer

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+j >= len(S):
            break
        elif S[i+j] == T[j] or S[i+j] == '?':
            match += 1
        else:
            break
    if match == len(T):
        idx.append(i)

if len(idx) == 0:
    print 'UNRESTORABLE'
else:
    # fill T
    prev_idx = len(S)
    for i in sorted(idx, reverse=True):
        if i + len(T) - 1 >= prev_idx:
            continue
        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: Wrong Answer

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

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:
                scand = s
                for k in range(len(t)):
                    str_list=list(scand)
                    str_list[i+k]=t[k]
                    scand="".join(str_list)

if s == scand:
    print("UNRESTORABLE")
else:
    print(filla(scand))

Submission status: Wrong Answer

Solution code:
import sys

s = raw_input()
key = raw_input()

index = s.find(key[0])

if index < 0:
    print "UNRESTORABLE"
    sys.exit()
else:
    tmp = s[:index] + key

ans = ""
for i in tmp:
    if i == '?':
        ans = ans + 'a'
    else:
        ans = ans + i

print ans

Submission status: Wrong Answer

Solution code:
## -*- coding:utf-8
#import os
#import sys
#import re
#import deque

SD=input().rstrip()
T=input().rstrip()
S=""

sdlen=len(SD)
tlen=len(T)
for i in range(sdlen-tlen+1):
    s=SD[i:i+tlen]
    #print(s)
    flag=True
    for j,k in zip(s,T):
        if( j=="?" ):
            continue
        if( j==k ):
            continue
        else:
            flag=False
            break
    if(flag==True):
        # 部分文字列一致
        S=(SD[0:i]+T+SD[i+tlen:]).replace('?','a')
        break
print(("UNRESTORABLE" if len(S)==0 else S),flush=True)

Submission status: Wrong Answer

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

flag = 0
count = 0
for i in range(len(s)):
    if s[i] == '?' or s[i] in t:
        if count == 0:
            start = i
        count += 1
    else:
        count = 0
    if count == len(t):
        s = s[:start] + t + s[start+len(t)+1:]
        flag = 1
        break

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

Submission status: Wrong Answer

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 + ls], t)
        if m is None:
            continue
        ans.append((s[:i] + t + s[i + ls:]).replace('.', 'a'))
    if not ans:
        return 'UNRESTORABLE'
    return min(ans)


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

print(solve(s, t))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def get_ln_inputs():
    return input().split()


def map_list(fn, xs):
    return list(map(fn, xs))


def get_ln_int_inputs():
    return map_list(int, get_ln_inputs())


def possible_to_insert(S, T, index):
    if index + len(T) > len(S):
        return False
    for i in range(len(T)):
        if S[index + i] != "?" and S[index + i] != T[i]:
            return False
    return True


def main():
    S = get_ln_inputs()[0]
    T = get_ln_inputs()[0]

    ins_idx = -1
    for i in range(len(S)):
        if possible_to_insert(S, T, i):
            ins_idx = i
            break

    if ins_idx == -1:
        print("UNRESTORABLE")
        return

    S = S[:ins_idx] + T + S[ins_idx + len(T):]
    print(S.replace("?", "a"))

    return


main()

Submission status: Wrong Answer

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
print(ans.replace('?', 'a'))

Submission status: Wrong Answer

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
		else:
			s[j]=t[j-i]
	if flag:
		ans=""
		for j in s:
			if j=='?':
				ans+="a"
			else:
				ans+=j
		print(ans)
		break
else:
	print("UNRESTORABLE")

Submission status: Time Limit Exceeded

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

flag = 0
if t in s:
  s = s.replace('?', 'a')
  print(s)
  flag = 1
if '?' * len(t) in s:
  s = s[::-1]
  s = s.replace('?' * len(t), t[::-1], 1)
  s = s.replace('?', 'a')
  print(s[::-1])
  flag = 1          

if flag == 0:
  for i in range(0, 2 ** len(t)):
    tmp = '0' * (len(t) - len(bin(i)[2:])) + bin(i)[2:]
    lst = []
    for j, elem in enumerate(tmp):
      if elem == '0':
        lst.append('?')
      else:
        lst.append(t[j])
    tmp2 = ''.join(lst)
    if tmp2 in s:
      s = s[::-1]
      s = s.replace(tmp2[::-1], t[::-1], 1)
      s = s.replace('?', 'a')
      print(s[::-1])
      flag = 1
      break      
    
if flag == 0:
	print('UNRESTORABLE')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
original_S=input()
original_T=input()

S=deque(original_S)
T=deque(original_T)
restored_S=deque()

while len(S)>=len(T)>0:
    s=S.pop()
    t=T.pop()

    if s==t or s=='?':
        restored_S.appendleft(t)

    else:
        copied_S=deque(original_S)
        re_restored_S=deque()
        for n in range(len(restored_S)):
            s2=copied_S.pop()
            if s2=='?':
                re_restored_S.appendleft('a')
            else:
                re_restored_S.appendleft(s2)
        restored_S=re_restored_S
        S.append(s)
        T=deque(original_T)

if len(T)>0:
    print('UNRESTORABLE')

else:
    while len(S)>0:
        s=S.pop()
        if s=='?':
            restored_S.appendleft('a')
        else:
            restored_S.appendleft(s)
    print(''.join(list(restored_S)))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]


def main():

    S = input()
    T = input()
    len_T = len(T)
    idx = -1
    for i in range(2**len_T):
        tmp = []
        for j in range(len_T):
            if i>>j & 1:
                tmp.append(T[j])
            else:
                tmp.append('?')
        idx = max(idx, S.rfind(''.join(tmp)))
    if idx == -1:
        print('UNRESTORABLE')
    else:
        ans = list(S.replace('?','a'))
        for i,t in enumerate(T):
            ans[idx+i] = t
        print(''.join(ans))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

S_dash = input()
T = input()

S_dash_list = list(S_dash)
T_list = list(T)

ei = len(S_dash_list)
si = ei - len(T_list)

insert_flag = False
while si >= 0:
    #print('si: {}, ei: {}'.format(si, ei))
    target = S_dash_list[si:ei]
    flag = True
    for i in reversed(range(len(T_list))):
        if S_dash_list[si + i] != T_list[i] and S_dash_list[si + i] != '?':
            flag = False
            # ここでsiとeiを更新
            ei = si + i + 1
            si = ei - len(T_list)
            break
    if flag:
        for i in range(len(T_list)):
            S_dash_list[si + i] = T_list[i]
        insert_flag = True
        break

if not insert_flag:
    print('UNRESTORABLE')
else:
    ans = ''.join(S_dash_list)
    #print(ans)

    # '?'をaで埋める
    print(ans.replace('?', 'a'))

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

def get_t_strs(T):
  lenT = len(T)
  strs = ['?'*lenT, T]
  for i in range(1,lenT):
    cmbs = list(combinations([i for i in range(lenT)],i))
    for cmb in cmbs:
      T_list = [t for t in T]
      for idx in cmb: T_list[idx] = '?'
      strs.append(''.join(T_list))
  return strs

S,T = input(), input()
if S.count('?') == 0:
  print(S)
  exit()

idx_options = []
t_strs = get_t_strs(T)
for t_str in t_strs:
  idx = S.rfind(t_str)
  if idx != -1: idx_options.append(idx+1)

if len(idx_options) == 0: print('UNRESTORABLE')
else:
  max_idx = max(idx_options)
  print((S[:max_idx-1] + T + S[max_idx+len(T)-1:]).replace('?','a'))

Submission status: Time Limit Exceeded

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

if len(s) < len(t):
  print("UNRESTORABLE")
  exit()

c=len(s)-len(t)

flg=False
while True:
  if c<0:
    break
  
  flg2=True
  for i in range(len(t)):
    if s[c+i]!=t[i] and s[c+i]!="?":
      flg2=False
  if flg2:
    flg=True
    break
# c-=1
#print(c)



if flg:
  print((s[:c]+t+s[c+len(t):]).replace("?","a"))
else:
  print("UNRESTORABLE")

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ns,nt,nd=len(s),len(t),len(s)-len(t)
ans="z"*ns
flag=0
for i in range(2**nt):
  K=str(bin(i))[2:].zfill(nt)
  T=""
  for j in range(nt):
    if K[j]=="0":
      T+="?"
    else:
      T+=t[j]
  for k in range(nd+1):
    if s[k:].startswith(T):
      Key=s[:k]+t+s[k+nt:]
      ans=min(ans,Key.replace("?","a"))
      flag=1
print(ans if flag==1 else "UNRESTORABLE")

Submission status: Time Limit Exceeded

Solution code:
s=input()
t=input()
ans="z"*len(s)
flag=0
for i in range(2**len(t)):
  K=str(bin(i))[2:].zfill(len(t))
  T=""
  for j in range(len(t)):
    if K[j]=="0":
      T+="?"
    else:
      T+=t[j]
  for k in range(len(s)-len(t)+1):
    if s[k:k+len(t)]==T:
      Key=s[:k]+t+s[k+len(t):]
      ans=min(ans,Key.replace("?","a"))
      flag=1
print(ans if flag==1 else "UNRESTORABLE")

Submission status: Time Limit Exceeded

Solution code:
S_raw = input()
T_raw = input()

S = list(S_raw)
T = list(T_raw)

i = 0
j = 0

j_list = []
S_list = []

lt = len(T)
ls = len(S)

while True:
	if j == ls or i == lt:
		if not i == lt:
			print("UNRESTORABLE")
			exit(0)
		elif j != ls:
			j_list.append(j)
			i = 0
			j = j - lt 
		else:
			j_list.append(j)
			break

	if T[i] == S[j]:
		i += 1
		j += 1
	elif S[j] == '?':
		i += 1
		j += 1
	else:
		i = 0
		j += 1


for j in j_list:
	for i,c in zip(range(j-lt,j),T):
		S[i] = c

	S_tmp = ''

	for i in range(ls):
		if S[i] == '?':
			S_tmp += 'a'
		else:
			S_tmp += str(S[i])

	S_list.append(S_tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

def make_pattern(s):
    res = []
    for i in range(2**len(s)):
        origin = s
        for j in range(len(s)):
            if ((i & 1) == 1) and (j != 0) and (j != (len(s) - 1)):
                origin = origin[:j] + "?" + origin[(j+1):]
            elif ((i & 1) == 1) and (j == 0):
                origin = "?" + origin[1:]
            elif ((i & 1) == 1) and (j == (len(s) - 1)):
                origin = origin[:len(s) - 1] + "?"
            i = i >> 1
        res.append(origin)
    return res

S = sys.stdin.readline().strip()
T = sys.stdin.readline().strip()

if S.find(T) > -1:
    ans = S.replace("?", "a")
    print(ans)
else:
    pattern_list = make_pattern(T)
    index_list = []
    for pattern in pattern_list:
        index = S.rfind(pattern)
        if index != -1:
            index_list.append(index)
    if len(index_list) == 0:
        print ("UNRESTORABLE")
        sys.exit()
    replace_index = max(index_list)
    ans = S[:(replace_index)] + T + S[(replace_index + len(T)):]
    ans = ans.replace("?", "a")
    print(ans)

Submission status: Accepted

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

#import
#import math
#import numpy as np
#= int(input())
S = list(input())
T = list(input())

ls = len(S); lt = len(T)

for i in range(ls - lt, -1, -1):
    isok = True
    for j in range(lt):
        if S[i + j] == "?":
            continue
        if S[i + j] != T[j]:
            isok = False
            break
    if isok:
        S[i:i+lt] = T
        ans = ""
        for s in S:
            if s == "?":
                ans += "a"
            else:
                ans += s
        print(ans)
        exit()

print("UNRESTORABLE")

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())
NS,NT = len(S),len(T)
outs = []
if NS>=NT:
    for i in range(NS-NT+1):
        flag = 0
        for j in range(NT):
            if S[i+j]==T[j] or S[i+j]=="?":
                continue
            else:
                flag = 1
                break
        if flag==0:
            out = ["a"]*NS
            for j in range(NT):
                out[i+j]=T[j]
            for j in range(NS):
                if S[j]!="?":
                    out[j]=S[j]
            outs.append("".join(out))

if len(outs) == 0:
    print("UNRESTORABLE")
else:
    print(outs[-1])

Submission status: Accepted

Solution code:
S = list(input())
T = list(input())
NS,NT = len(S),len(T)
outs = []
if NS>=NT:
    for i in range(NS-NT+1):
        flag = 0
        for j in range(NT):
            if S[i+j]==T[j] or S[i+j]=="?":
                continue
            else:
                flag = 1
                break
        if flag==0:
            out = ["a"]*NS
            for j in range(NT):
                out[i+j]=T[j]
            for j in range(NS):
                if S[j]!="?":
                    out[j]=S[j]
            outs.append("".join(out))

if len(outs) == 0:
    print("UNRESTORABLE")
else:
    outs.sort()
    print(outs[0])

Submission status: Accepted

Solution code:
import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array

# 時々使う
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


MOD = 10 ** 9 + 7
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    T = iss()

    ret = set()
    for i in range(len(S)-len(T)+1):
        for s, t in zip(S[i:i+len(T)], T):
            if s == t or s == '?': continue
            else: break
        else:
            tmp = ''
            if i != 0: tmp += S[:i]
            tmp += T
            if i+len(T) < len(S): tmp += S[i+len(T):]
            ret.add(tmp.replace('?', 'a'))

    if len(ret) == 0:
        print('UNRESTORABLE')
    else:
        print(sorted(list(ret))[0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
s = input()
t = input()
l = []
for i in range(len(s)-len(t)+1):
    for j in range(i, i+len(t)):
        if s[j] != "?" and s[j] != t[j-i]:
            break
    else:
        l.append(s[:i]+t+s[i+len(t):])
if len(l) == 0:
    print("UNRESTORABLE")
    exit()
l.sort()
print(l[0].replace("?", "a"))