Problem:


Score : 500 points

Problem Statement

Snuke has a string s.
From this string, Anuke, Bnuke, and Cnuke obtained strings a, b, and c, respectively, as follows:

Choose a non-empty (contiguous) substring of s (possibly s itself). Then, replace some characters (possibly all or none) in it with ?s.

For example, if s is mississippi, we can choose the substring ssissip and replace its 1-st and 3-rd characters with ? to obtain ?s?ssip.

You are given the strings a, b, and c.
Find the minimum possible length of s.

Constraints

1 \leq |a|, |b|, |c| \leq 2000

a, b, and c consists of lowercase English letters and ?s.

Input

Input is given from Standard Input in the following format:

a
b
c

Output

Print the minimum possible length of s.

Sample Input 1

a?c
der
cod

Sample Output 1

7

For example, s could be atcoder.

Sample Input 2

atcoder
atcoder
???????

Sample Output 2

7

a, b, and c may not be distinct.



Sample input:
a?c
der
cod


Sample output:
7

Submission status: Runtime Error

Solution code:
def comp(a,b,c=repeat("?")):
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a, b, c))

def comp_dup(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return comp(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

def merge1(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge2(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b, a[-lb+i:]):
      yield la-lb+i
  yield la

def merge3(a,b):
  la, lb = map(len,[a,b])
  for i in range(1,lb):
    if comp(b[i:], a):
      yield -i
  yield -lb
  
  
  
def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  la, lb, lc = map(len,[a,b,c])
  abc = float("inf")
  a_b = list(merge1(a,b))
  a_b2 = list(merge2(a,b))
  a_b3 = list(merge3(a,b))
  a_c = list(merge1(a,c))
  a_c2 = list(merge2(a,c))
  a_c3 = list(merge3(a,c))
  b_c = list(merge1(b,c))
  b_c2 = list(merge2(b,c))
  b_c3 = list(merge3(b,c))
  
  for i in a_b:
    for j in a_c:
      if j+lc <= i or i+lb <= j:
        return la
      if j-i in (b_c+b_c2+b_c3) and comp_dup(0,i,j,a,b,c):
        return la
        
  for i in a_b:
    for j in a_c2:
      if i+lb <= j:
        abc = min(abc, j+lc)
        break
      if j-i in (b_c2) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, j+lc)
        break
    for j in a_c3:
      if j+lc <= i:
        abc = min(abc, la-j)
        break
      if j-i in (b_c3) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, la-j)
        break
  
  for i in a_b2:
    if abc <= i+lb:
      break
    for j in a_c+a_c2:
      if j+lc  <= i:
        abc = min(abc, i+lb)
        break
      if j-i in (b_c+b_c3) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, i+lb)
        break
    if abc <= i+lb:
      break
    if b_c and la <= i+b_c[-1]:
      abc = min(abc, i+lb)
      break
    
    for j in a_c3:
      if abc <= i-j+lb:
        break
      if j+lc <= i:
        abc = min(abc, i-j+lb)
        break
      if j-i in b_c3 and comp_dup(0,i,j,a,b,c):
        abc = min(abc, i-j+lb)
        break
        
    for j in b_c2:
      if abc <= i+j+lc:
        break
      if la <= i+j:
        abc = min(abc, i+j+lc)
        break
      if i+j in a_c2 and comp_dup(0,i,i+j,a,b,c):
        abc = min(abc, i+j+lc)
        break
      
      
  for i in a_b3:
    if abc <= la-i:
      break
    for j in a_c+a_c3:
      if i+lb <= j:
        abc = min(abc, la-i)
        break
      if j-i in (b_c+b_c2) and comp_dup(0,i,j,a,b,c):
        abc = min(abc, la-i)
        break
    if abc <= la-i:
      break
    if b_c and i+b_c[0]+lc <= 0:
      abc = min(abc, la-i)
      break
      
    for j in a_c2:
      if abc <= j-i+lc:
        break
      if i+lb <= j:
        abc = min(abc, j-i+lc)
        break
      if j-i in b_c2 and comp_dup(0,i,j,a,b,c):
        abc = min(abc, j-i+lc)
        break
        
    for j in b_c3:
      if abc <= la-i-j:
        break
      if i+j+lc <= 0:
        abc = min(abc, la-i-j)
        break
      if i+j in a_c3 and comp_dup(0,i,i+j,a,b,c):
        abc = min(abc, la-i-j)
        break
      
  
  for i in range(1,lc):
    if abc <= la+lb+i:
      break     
    for j in a_c2:
      if j-la-i in b_c3:
        return la+lb+i
    for j in b_c2:
      if j-la-i in a_c3:
        return la+lb+i
    
  return abc

a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
import sys

def Z_algo2(s):
    ls = len(s)
    lcp = [0]*ls
    lcp[0] = ls
    i,j = 1,0
    while i < ls:
        while i+j < ls and (s[j] == s[i+j] or s[j] == '?' or s[i+j] == '?'):
            j += 1
        lcp[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < ls and k + lcp[k] < j:
            lcp[i+k] = lcp[k]
            k += 1
        i += k
        j -= k
    return lcp

def Z_algo(s,t):
    lt = len(t)
    ls = len(s)
    l = [0]*lt
    for i in range(len(t)):
        j = 0
        while j < ls and i+j < lt and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
            j += 1
        l[i] = j
    return l

def main():
    stdin = sys.stdin

    ns = lambda: stdin.readline().rstrip()
    ni = lambda: int(stdin.readline().rstrip())
    nm = lambda: map(int, stdin.readline().split())
    nl = lambda: list(map(int, stdin.readline().split()))

    a = list(map(ord, list(ns())))
    b = list(map(ord, list(ns())))
    c = list(map(ord, list(ns())))

    l = [a, b, c]
    g = [[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            if i != j:
                g[i][j] = Z_algo(l[i],l[j])
    ans = sum(len(x) for x in l)
    for i in range(3):
        lli = len(l[i])
        for j in range(3):
            if i == j: continue
            k = 3-i-j
            llj = len(l[j])
            llk = len(l[k])
            li = [ii for ii in range(lli) if g[j][i][ii] >= min(lli - ii, llj)]
            lj = [ii for ii in range(lli) if g[k][j][ii] >= min(llj - ii, llk)]
            lk = [ii for ii in range(lli) if g[k][i][ii] >= min(lli - ii, llk)]
            if li:
                c = max(lli, min(li) + llj + llk)
                if ans > c: ans = c
            for ii in li:
                for jj in lj:
                    kk = ii + jj
                    if kk >= lli or g[k][i][kk] >= min(lli - kk, llk):
                        c = max(lli, ii + llj, kk + llk)
                        if ans > c: ans = c
            for ii in li:
                for kk in lk:
                    if kk < ii + len(l[j]): continue
                    c = max(lli, ii + llj, kk + llk)
                    if ans > c: ans = c
    print(ans)

if __name__ == "__main__":
    ques = ord('?')
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            li = len(s[i])
            for j in range(i, 3):
                lj = len(s[j])
                for k in range(li):
                    ok = True
                    for ni in range(k, len(li):
                        nj = ni - k
                        if nj >= lj:
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            ok = False
                    d[i][j][k] = ok
        f = lambda i, j, k: True if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if not f(0, 1, x):
                    continue
                if not f(1, 2, y):
                    continue
                if not f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                ans = min(ans, now)
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*n for _ in range(3)] for _ in range(3)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            for j in range(i, 3):
                for k in range(len(s[i])):
                    ok = True
                    for ni in range(k, len(s[i])):
                        nj = ni - k
                        if nj > len(s[j]):
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            ok = False
                    d[i][j][k] = ok
        f = lambda i, j, k: True if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if not f(0, 1, x):
                    continue
                if not f(1, 2, y):
                    continue
                if not f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                ans = min(ans, now)
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from itertools import permutations
"""
どの順番に出てくるかをすべて（6通り）ためす
そこからa,b,cのずれ幅の組み合わせ（2000**2）をためす
判定をO(1)ですると
2000*2*6 = 2.4*10**7
x: aとbのずれ幅
y: aとcのずれ幅
"""
def main():
    ss = sorted([input() for _ in range(3)])
    n = len(max(ss, key=len))
    d = [[[None]*3 for _ in range(3)] for _ in range(n)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            for j in range(i, 3):
                for k in range(len(s[i])):
                    ok = True
                    for ni in range(k, len(s[i])):
                        nj = ni - k
                        if nj > len(s[j]):
                            break
                        if s[i][ni] == "?" or s[j][nj] == "?":
                            continue
                        if s[i][ni] != s[j][nj]:
                            ok = False
                    d[i][j][k] = ok
        f = lambda i, j, k: True if k>=len(s[i]) else d[i][j][k]
        for x in range(n):
            for y in range(n):
                if not f(0, 1, x):
                    continue
                if not f(1, 2, y):
                    continue
                if not f(0, 2, x+y):
                    continue
                now = max([0, len(s[0]), x+len(s[1]), x+y+len(s[2])])
                ans = min(ans, now)
    print(ans)
                
if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def solve(a: str, b: str, c: str):
    permutation = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]
    abc = (a,b,c)
    ans = 10**4

    for i_1,j_1,k_1 in permutation:
        A = abc[i_1]
        B = abc[j_1]
        C = abc[k_1]
        LENA = len(A)
        LENB = len(B)
        LENC = len(C)

        AB = [False]*(LENA+1)
        BC = [False]*LENB+[True]*2000
        AC = [False]*(LENA)+[True]*(2010)
        AB[-1] = True
        BC[LENB] = True

        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENB+i)):
                if A[j] != B[j-i] and A[j] != "?" and B[j-i] != "?":
                    break
            else:
                AB[i] = True

        for i in range(LENB): # Bのindex
            for j in range(i,min(LENB,LENC+i)):
                if B[j] != C[j-i] and B[j] != "?" and C[j-i] != "?":
                    break
            else:
                BC[i] = True

        for i in range(LENA): # Aのindex
            for j in range(i,min(LENA,LENC+i)):
                if A[j] != C[j-i] and A[j] != "?" and C[j-i] != "?":
                    break
            else:
                AC[i] = True        
        # x: AとBがどれだけずれてるか
        # y: BとCがどれだけずれてるか
        length = 10**4
        for x in range(LENA+1):
            for y in range(2001+1):
                if AB[x] and BC[y] and AC[x+y]:
                    length = min(length,max(LENA,x+LENB,x+y+LENC))
        ans = min(ans,length)
 
    print(ans)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    a = next(tokens)  # type: str
    b = next(tokens)  # type: str
    c = next(tokens)  # type: str
    solve(a, b, c)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# E - Three Substrings

a = list(input())
b = list(input())
c = list(input())

A, B, C = len(a), len(b), len(c)

M = max(A, B, C)
cons = 3*M + 10
rel_match_b_against_a = [True] * 2 * cons
rel_match_b_against_c = [True] * 2 * cons
rel_match_c_against_a = [True] * 2 * cons

for rel_idx in range(-B+1, A):
    if rel_idx < 0:
        for i in range(min(A, rel_idx + B)):
            if a[i] != b[i + rel_idx] and a[i] != "?" and b[i + rel_idx] != "?":
                rel_match_b_against_a[rel_idx + cons] = False
                break
    else:
        for i in range(min(A - rel_idx, B)):
            if a[i + rel_idx] != b[i] and a[i + rel_idx] != "?" and b[i] != "?":
                rel_match_b_against_a[rel_idx + cons] = False
                break

for rel_idx in range(-B+1, C):
    if rel_idx < 0:
        for i in range(min(C, rel_idx + B)):
            if c[i] != b[i + rel_idx] and c[i] != "?" and b[i + rel_idx] != "?":
                rel_match_b_against_c[rel_idx + cons] = False
                break
    else:
        for i in range(min(C - rel_idx, B)):
            if c[i + rel_idx] != b[i] and c[i + rel_idx] != "?" and b[i] != "?":
                rel_match_b_against_c[rel_idx + cons] = False
                break

for rel_idx in range(-C+1, A):
    if rel_idx < 0:
        for i in range(min(A, rel_idx + C)):
            if a[i] != c[i + rel_idx] and a[i] != "?" and c[i + rel_idx] != "?":
                rel_match_c_against_a[rel_idx + cons] = False
                break
    else:
        for i in range(min(A - rel_idx, C)):
            if a[i + rel_idx] != c[i] and a[i + rel_idx] != "?" and c[i] != "?":
                rel_match_c_against_a[rel_idx + cons] = False
                break

ans = 3*M
for rel_idx_b_against_a in range(-2*M, 2*M):
    for rel_idx_c_against_a in range(-2*M, 2*M):
        if rel_match_b_against_a[rel_idx_b_against_a + cons] and rel_match_c_against_a[rel_idx_c_against_a + cons] and rel_match_b_against_c[rel_idx_b_against_a - rel_idx_c_against_a + cons]:
            ans = min(ans, max(A, B + rel_idx_b_against_a, C + rel_idx_c_against_a) - min(0, rel_idx_b_against_a, rel_idx_c_against_a))

print(ans)

Submission status: Runtime Error

Solution code:
a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[j]!='?':
      flag_ab[i-j+(len_b+len_c)]=False
flag_ac=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[j]!='?':
      flag_ac[i-j+(len_b+len_c)]=False
flag_bc=[True]*(2*(len_b+len_c)+1)
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[j]!='?':
      flag_bc[i-j+(len_b+len_c)]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+(len_b+len_c)] and flag_ac[left_c-left_a+(len_b+len_c)] and flag_bc[left_c-left_b]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)

Submission status: Runtime Error

Solution code:
a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[j]!='?':
      flag_ab[i-j+(len_b+len_c)]=False
flag_ac=[True]*(2*(len_b+len_c)+1)
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[j]!='?':
      flag_ac[i-j+(len_b+len_c)]=False
flag_bc=[True]*(2*(len_b+len_c)+1)
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[j]!='?':
      flag_bc[i-j+(len_b+len_c)]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+(len_b+len_c)] and flag_ac[left_c-left_a+(len_b+len_c)] and flag_bc[left_c-left_b+(len_b+len_c)]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)

Submission status: Runtime Error

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(abs(lr),len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  ab = len(a)+len(b)
  abc = float("inf")
  for d in merge(a,b):
    if len(d) > abc:
      break
    l = len(next(merge(d, c)))
    abc = min(abc, l)
  if abc <= ab:
    return abc
  
  for i in range(1,min(len(c),abc-ab)):
    for j in range(1,len(c)):
      if comp(a[-j:]+"?"*i+b, c):
        return ab+i
      if comp(b[-j:]+"?"*i+a, c):
        return ab+i
  return abc

a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for i in range(abs(lr),len(b)):
    m = comp(b[i:], a)
    if m:
      yield  b[:i]+m+a[len(b)-i:]
    m = comp(b, a[-len(b)+i:])
    if m:
      yield a[:-len(b)+i]+m+b[-i:]
  yield a+b
  yield b+a

def merge2(a,b,lr=0):
  for i in range(abs(lr),len(b)):
    if lr>=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], i
    if lr<=0:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], -i
  yield a+b, len(b)
  yield b+a, -len(b)

def min_merge(a,b,c):
  a,b,c=sorted([a,b,c],key=len,reverse=True)
  ab = len(a)+len(b)
  abc = float("inf")
  for d in merge(a,b):
    if len(d) > abc:
      break
    l = len(next(merge(d, c)))
    abc = min(abc, l)
  if abc <= ab:
    return abc
  
  for i in range(1,min(len(c),abc-ab)):
    for j in len(1,c):
      if (comp(a[-j:]+"?"*i+b)):
        return ab+i
      if (comp(b[-j:]+"?"*i+a)):
        return ab+i
  return abc
a=input()
b=input()
c=input()

print(min_merge(a,b,c))

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
A=input()
B=input()
C=input()

a,b,c=len(A),len(B),len(C)

def f(X,Y):
  XY=[True]*(10**4)
  x,y=len(X),len(Y)
  for i in range(5000-y+1,5000+x):
    ret=True
    if i<=5000:
      for j in range(min(x,y+i-5000)):
        if X[j]=="?" or Y[j-i+5000]=="?" or X[j]==Y[j-i+5000]:
          continue
        else:
          ret=False
    else:
      for j in range(min(y,x-i+5000)):
        if Y[j]=="?" or X[j+i-5000]=="?" or Y[j]==X[j+i-5000]:
          continue
        else:
          ret=False
    XY[i]=ret
  return XY
AB=f(A,B)
BC=f(B,C)
AC=f(A,C)
ans=a+b+c
for i in range(5000-b-c,5000+a+c):
  if AB[i]:
    for j in range(5000-b-c,5000+a+b):
      if -4000<=j-i<=4000:
        if AC[j] and BC[j-i+5000]:
          l=min(5000,i,j)
         r=max(i+b,j+c,5000+a)
          ans=min(ans,r-l)
      else:
        if AC[j]:
          l=min(5000,i,j)
          r=max(i+b,j+c,5000+a)
          ans=min(ans,r-l)
print(ans)

Submission status: Runtime Error

Solution code:
def match(x, y):
    return x == y or x == '?' or y == '?'


def check(s, t):
    ANS = [1] * (10 ** 4)
    S = len(s); T = len(t)
    for i in range(S):
        for j in range(T):
            if not match(s[i], t[j]):
                ANS[i - j + 5000] = 0
    return ANS


def solve(a, b, c):
    lenA = len(a)
    lenB = len(b)
    lenC = len(c)

    AB = check(a, b)
    AC = check(a, c)
    BC = check(b, c)

    ans = lenA + lenB + lenC
    for i in range(-lenB, lenA + lenB + 1):
        for j in range(-lenC, lenA + lenC + 1):
            if AB[i + 5000] and AC[j + 5000] and BC[j - i + 5000]:
                L = min(0, min(i, j))
                R = max(lenA, max(lenB + i, lenC + j))
                ans = min(ans, R - L)

    return ans


a = input()
b = input()
c = input()


ans = min(solve(a, b, c), min(solve(b, c, a), solve(c, a, b)))

print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
A=input()
B=input()
C=input()

a,b,c=len(A),len(B),len(C)

def f(X,Y):
  XY=[True]*(10**4)
  x,y=len(X),len(Y)
  for i in range(5000-y+1,5000+x):
    ret=True
    if i<=5000:
      for j in range(min(x,y+i-5000)):
        if X[j]=="?" or Y[j-i+5000]=="?" or X[j]==Y[j-i+5000]:
          continue
        else:
          ret=False
    else:
      for j in range(min(y,x-i+5000)):
        if Y[j]=="?" or X[j+i-5000]=="?" or Y[j]==X[j+i-5000]:
          continue
        else:
          ret=False
    XY[i]=ret
  return XY
AB=f(A,B)
BC=f(B,C)
AC=f(A,C)
ans=a+b+c
for i in range(5000-b-c,5000+a+c):
  for j in range(5000-b-c,5000+a+b):
    if AB[i] and AC[j] and BC[j-i+5000]:
      l=min(5000,i,j)
      r=max(i+b,j+c,5000+a)
      ans=min(ans,r-l)
print(ans)

Submission status: Runtime Error

Solution code:
def main():
    a = input()
    b = input()
    c = input()
    A, B, C = len(a), len(b), len(c)
    ab = [True]*10000
    ac = [True]*10000
    bc = [True]*10000

    def check(c1, c2):
        if c1 == '?' or c2 == '?' or c1 == c2:
            return False
        return True

    for i in range(A):
        for j in range(B):
            if check(a[i], b[j]):
                ab[i-j+5000] = False
    for i in range(A):
        for j in range(C):
            if check(a[i], c[j]):
                ac[i-j+5000] = False
    for i in range(B):
        for j in range(C):
            if check(b[i], c[j]):
                bc[i-j+5000] = False
    ans = A + B + C
    for i in range(-(B+C), A+C):
        for j in range(-(B+C), A+B):
            if ab[i+5000] and ac[j+5000] and bc[j-i+5000]:
                L = min(0, i, j)
                R = max(A, i+B, j+C)
                ans = min(ans, R - L)
    print(ans)


main()

Submission status: Runtime Error

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for m, lr in merge2(a,b):
    yield m

def merge2(a,b,lr=0):
  for i in range(abs(lr),len(b)):
    if lr>=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], i
    if lr<=0:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], -i
  yield a+b, len(b)
  yield b+a, -len(b)

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d, lr in merge2(a,c):
  if len(d) > abc:
    break
  if lr > 0:
    lr = leb(b)+1-lr
  else:
    lr = -leb(b)-1-lr
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)

Submission status: Runtime Error

Solution code:
def comp(a,b):
  r=""
  for x,y in zip(a,b):
    if x==y:
      r += x
    elif y=="?":
      r += x
    elif x=="?":
      r += y
    else:
      return False
  return r

def merge(a,b):
  for i in range(len(a)-len(b)+1):
    m = comp(a[i:],b)
    if m:
      yield a[:i]+m+a[i+len(b):]
  
  for m, lr in merge2(a,b):
    yield m

def merge2(a,b,lr=0):
  for i in range(abs(lr),len(b)):
    if lr>=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], i
    if lr<=0:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], -i
  yield a+b, len(b)
  yield b+a, -len(b)

a=input()
b=input()
c=input()
a,b,c=sorted([a,b,c],key=len,reverse=True)

abc = float("inf")
for d in merge(a,b):
  if len(d) > abc:
    break
  l = len(next(merge(d, c)))
  abc = min(abc, l)

for d, lr in merge2(a,c):
  if len(d) > abc:
    break
  if lr > 0:
    lr = b+1-lr
  else:
    lr = -b-1-lr
  l = len(next(merge2(d, b, lr))[0])
  abc = min(abc, l)

print(abc)

Submission status: Runtime Error

Solution code:
# E. Three Substrings
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e
a = input()
b = input()
c = input()

al = len(a)
bl = len(b)
cl = len(b)

#M = 2000
M = max(al, bl, cl)

# All possible places
ab = [True] * (6 * M + 1)
ac = [True] * (6 * M + 1)
bc = [True] * (6 * M + 1)

def match(x, y):
    return (x == '?' or y == '?' or x == y)

for i in range(al):
    for j in range(bl):
        if not match(a[i], b[j]):
            # Single unmatch block in overlapping region block possibility
            #  > Single (i-j+M) index with many (i, j) pair checking.
            ab[i-j+2*M] = False

for i in range(al):
    for j in range(cl):
        if not match(a[i], c[j]):
            ac[i-j+2*M] = False

for i in range(bl):
    for j in range(cl):
        if not match(b[i], c[j]):
            bc[i-j+2*M] = False


lowest = 3 * M
for i in range(-2*M, 2*M+1):
    for j in range(-2*M, 2*M+1):
        # Check all possible place including between spaces
        if ab[i+2*M] and ac[j+2*M] and bc[j-i+2*M]:
            L = min(0, min(i, j))
            R = max(al, max(bl+i, cl+j))
            lowest = min(lowest, R - L)

print(lowest)

Submission status: Runtime Error

Solution code:
a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*20000
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[i]!='?':
      flag_ab[i-j+10000]=False
flag_ac=[True]*20000
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[i]!='?':
      flag_ac[i-j+10000]=False
flag_bc=[True]*20000
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[i]!='?':
      flag_bc[i-j+10000]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+10000] and flag_ac[left_c-left_a+10000] and flag_bc[left_c-left_b+10000]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)

Submission status: Runtime Error

Solution code:
a=tuple(input())
len_a=len(a)
b=tuple(input())
len_b=len(b)
c=tuple(input())
len_c=len(c)
flag_ab=[True]*10000
for i in range(len_a):
  for j in range(len_b):
    if a[i]!=b[j] and a[i]!='?' and b[i]!='?':
      flag_ab[i-j+5000]=False
flag_ac=[True]*10000
for i in range(len_a):
  for j in range(len_c):
    if a[i]!=c[j] and a[i]!='?' and c[i]!='?':
      flag_ac[i-j+5000]=False
flag_bc=[True]*10000
for i in range(len_b):
  for j in range(len_c):
    if b[i]!=c[j] and b[i]!='?' and c[i]!='?':
      flag_bc[i-j+5000]=False
ans=len_a+len_b+len_c
left_a=0
for left_b in range(-(len_b+len_c),len_b+len_c+1):
  for left_c in range(-(len_b+len_c),len_b+len_c+1):
    if flag_ab[left_b-left_a+5000] and flag_ac[left_c-left_a+5000] and flag_bc[left_c-left_b+5000]:
      right_a=left_a+len_a
      right_b=left_b+len_b
      right_c=left_c+len_c
      left=min(left_a,left_b,left_c)
      right=max(right_a,right_b,right_c)
      ans=min(ans,right-left)
print(ans)

Submission status: Runtime Error

Solution code:
# E. Three Substrings
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e
a = input()
b = input()
c = input()

al = len(a)
bl = len(b)
cl = len(b)

M = max(al, bl, cl)

# All possible places
ab = [True] * (4 * M + 1)
ac = [True] * (4 * M + 1)
bc = [True] * (4 * M + 1)

def match(x, y):
    return (x == '?' or y == '?' or x == y)

for i in range(al):
    for j in range(bl):
        if not match(a[i], b[j]):
            # Single unmatch block in overlapping region block possibility
            #  > Single (i-j+M) index with many (i, j) pair checking.
            ab[i-j+2*M] = False

for i in range(al):
    for j in range(cl):
        if not match(a[i], c[j]):
            ac[i-j+2*M] = False

for i in range(bl):
    for j in range(cl):
        if not match(b[i], c[j]):
            bc[i-j+2*M] = False

lowest = 3 * M
for i in range(-2*M, 2*M+1):
    for j in range(-2*M, 2*M+1):
        # Check all possible place including between spaces
        if ab[i+2*M] and ac[j+2*M] and bc[i-j+2*M]:
            L = min(0, min(i, j))
            R = max(al, max(bl+i, cl+j))
            lowest = min(lowest, R - L)

print(lowest)

Submission status: Runtime Error

Solution code:
# E. Three Substrings
# https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e
a = input()
b = input()
c = input()

print(a,b,c)
M = 2000

al = len(a)
bl = len(b)
cl = len(b)

# All possible places
ab = [True] * (4 * M + 1)
ac = [True] * (4 * M + 1)
bc = [True] * (4 * M + 1)

def match(x, y):
    return (x == '?' or y == '?' or x == y)

for i in range(al):
    for j in range(bl):
        if not match(a[i], b[j]):
            # Single unmatch block in overlapping region block possibility
            #  > Single (i-j+M) index with many (i, j) pair checking.
            ab[i-j+2*M] = False

for i in range(al):
    for j in range(cl):
        if not match(a[i], c[j]):
            ac[i-j+2*M] = False

for i in range(bl):
    for j in range(cl):
        if not match(b[i], c[j]):
            bc[i-j+2*M] = False

lowest = 3 * M
for i in range(-2*M, 2*M+1):
    for j in range(-2*M, 2*M+1):
        # Check all possible place including between spaces
        if ab[i+2*M] and ac[j+2*M] and bc[i-j+2*M]:
            L = min(0, min(i, j))
            R = max(al, max(bl+i, cl+j))
            lowest = min(lowest, R - L)

print(lowest)