Problem p02745 (python)

Fixed submission:
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import chain, permutations
from heapq import merge
from functools import wraps

def comp_wild(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def listify(fn):
  @wraps(fn)
  def wraper(*args, **kwargs):
    return list(fn(*args, **kwargs))
  return wraper

@listify
def includers(a,b):
  for i in range(len(a)-len(b)+1):
    if comp_wild(a[i:],b):
      yield i

@listify
def connectors(a,b):
  la = len(a)
  for i in range(max(la-len(b)+1, 1), la):
    if comp_wild(b, a[i-la:]):
      yield i
  yield la

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb", lambda:True)
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def iter_from(it, fm):
  return dropwhile(fm.__gt__, it)

def solve(a,b,c):
  keys = sorted((a,b,c), key=len, reverse=True)
  len_keys = list(map(len, keys))
  inc = {(i,j):includers(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  con = {(i,j):connectors(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in inc[0,1]:
    for j in inc[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or j-i in inc[1,2] or j-i in con[1,2] or i-j in con[2,1]:
        return len_keys[0]
  
  def candicates(x,y,z):
    return chain(
      
      (K(i+len_keys[z], cb=lambda:(
       (inc[x,y] and inc[x,y][0]+len_keys[y] <= i) or 
       (inc[z,y] and len_keys[x] <= i+inc[z,y][-1]) or 
       any((i-j in con[y,z] if i>j else j-i in inc[z,y]) for j in iter_from(inc[x,y]+con[x,y], i-len_keys[y]))
      )) for i in iter_from(con[x,z], len_keys[y]-len_keys[z]+1)),
      
      (K(min(i+next(iter_from(q, len_keys[x]-i+1))+len_keys[z] for i in p)) for (p, q) in [sorted((con[x,y], con[y,z]), key=len)]),
    )
  
  can = merge(*(candicates(*xyz) for xyz in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

print(solve(*(input() for _ in range(3))))

Buggy submission (verdict: Runtime Error):
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))
  
def comp33(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]) and comp(a[m-i:n-i],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp33(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *
from heapq import *

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  return 

def comp3(i,j,k,a,b,c):
  m = max(i,j,k)
  n = min(i+len(a),j+len(b),k+len(c))
  return all(len({x,y,z}-{"?"}) <= 1 for x,y,z in zip(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k]))

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

class K(int):
  def __new__(cls, *args, **kwargs):
    cb = kwargs.pop("cb")
    i = int.__new__(cls, *args, **kwargs)
    i.cb = cb
    return i

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    return chain(
      (K(i+len_keys[b], cb=lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp3(0,i,j,keys[a],keys[b],keys[c]) for j in dropwhile((i-len_keys[c]).__gt__, mid[a,c]+right[a,c]))
      )) for i in dropwhile((len_keys[c]-len_keys[b]+1).__gt__, right[a,b])),
      (K(min(i+next(dropwhile((len_keys[a]-i+1).__gt__, y))+len_keys[b] for i in x), cb=lambda:True) for (x, y) in [sorted((right[a,c], right[c,b]), key=len)]),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  for k in can:
    if k.cb():
      return k.i
  
  return sum(len_keys)

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *
from heapq import *
from collections import OrderedDict

def comp(a,b):
  return all(x==y or "?" in (x,y) for x,y in zip(a, b))

def comp3(a,b,c):
  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 comp3(a[m-i:n-i],b[m-j:n-j],c[m-k:n-k])

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

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

def delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid[1,2] or j-i in right[1,2] or i-j in right[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right[c,b] if i>j else j-i in mid[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))

  return sum(len_keys)

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *
from heapq import *
from collections import defaultdict

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 _merge_mid(a,b):
  la, lb = map(len,[a,b])
  for i in range(la-lb+1):
    if comp(a[i:],b):
      yield i

def merge_mid(a,b):
  return list(_merge_mid(a,b))

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

def merge_right(a,b):
  return list(_merge_right(a,b))

def iter_range(it, it_min, it_max=None):
  it = iter(it)
  for e in it:
    if e < it_min:
      continue
    else:
      if it_max is None or e < it_max:
        yield e
      break
  if it_max is not None:
    for e in it:
      if e >= it_max:
        return
      yield e
  else:
    for e in it:
      yield e

class K(object):
  def __init__(self,k, i, cb=None):
    self.i = i
    self.k = k
    self.cb = cb
  
  def __gt__(self, x):
    return self.i.__gt__(x.i)
  def __lt__(self, x):
    return self.i.__lt__(x.i)
  def __eq__(self, x):
    return self.i.__eq__(x.i)

def delay(f):
  yield f()

def min_merge(a,b,c):
  keys = sorted([a,b,c],key=len,reverse=True)
  len_keys = list(map(len, keys))
  mid = {(i,j):merge_mid(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  mid_set = {k:set(v) for k,v in mid.items()}
  right = {(i,j):merge_right(keys[i],keys[j]) for i,j in permutations(range(3), 2)}
  right_set = {k:set(v) for k,v in right.items()}
  
  for i in mid[0,1]:
    for j in mid[0,2]:
      if j+len_keys[2] <= i or i+len_keys[2] <= j or (j-i in mid_set[1,2]|right_set[1,2] or i-j in right_set[2,1]) and comp_dup(0,i,j,a,b,c):
        return len_keys[0]
  
  def candicates(a,b,c):
    x, y = (right[a,c], right[c,b]) if len(right[a,c]) > len(right[c,b]) else (right[c,b], right[a,c])
    return chain(
      (K((a,b,c),i+len_keys[b], lambda:(
       (mid[a,c] and mid[a,c][0]+len_keys[c] <= i) or (mid[b,c] and len_keys[a] <= i+mid[b,c][-1]) or 
       any((i-j in right_set[c,b] if i>j else j-i in mid_set[b,c]) and comp_dup(0,i,j,keys[a],keys[b],keys[c]) for j in iter_range(mid[a,c]+right[a,c], i-len_keys[c]))
      )) for i in iter_range(right[a,b], len_keys[c]-len_keys[b]+1)),
      delay(lambda:K((a,b,c),min(i+next(iter_range(x, len_keys[a]-i+1))+len_keys[b] for i in y), lambda:True)),
    )
  
  can = merge(*(candicates(x,y,z) for x,y,z in permutations(range(3),3)))
  
  return len_a + len_b + len_c

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *

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_b1, a_b2, a_b3  = map(list, [merge1(a,b), merge2(a,b), merge3(a,b)])
  a_b = {*a_b1, *a_b2, *a_b3}
  a_c1, a_c2, a_c3  = map(list, [merge1(a,c), merge2(a,c), merge3(a,c)])
  a_c = {*a_c1, *a_c2, *a_c3}
  b_c1, b_c2, b_c3  = map(list, [merge1(b,c), merge2(b,c), merge3(b,c)])
  b_c = {*b_c1, *b_c2, *b_c3}
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = (  
    chain(
      (lb+i for i in a_b2 if (a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2))),
      (lb+i for i in count(a_b2[-1]+1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2))),
    ),
    
    chain(
      (la-i for i in a_b3 if (b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3))),
      (la-i for i in count(a_b3[-1]-1, -1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3))),
    ),
    
    chain(
      (lc+i for i in a_c2 if (a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2))),
      (lc+i for i in count(a_c2[-1]+1) if any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2))),
    ),
    
    chain(
      (la-i for i in a_c3 if (a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3))),
      (la-i for i in count(a_c3[-1]-1, -1) if any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3))),
    ),
  )
  
  return min(map(next, can))

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
from itertools import *

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 seq(*seqs):
  for merge
  
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_b1, a_b2, a_b3  = map(list, [merge1(a,b), merge2(a,b), merge3(a,b)])
  a_b = {*a_b1, *a_b2, *a_b3}
  a_c1, a_c2, a_c3  = map(list, [merge1(a,c), merge2(a,c), merge3(a,c)])
  a_c = {*a_c1, *a_c2, *a_c3}
  b_c1, b_c2, b_c3  = map(list, [merge1(b,c), merge2(b,c), merge3(b,c)])
  b_c = {*b_c1, *b_c2, *b_c3}
  
  for i in a_b1:
    for j in a_c1:
      if j+lc <= i or i+lb <= j or j-i in b_c and comp_dup(0,i,j,a,b,c):
        return la
  
  can = (  
    chain(
      (lb+i for i in a_b2 if (a_c1 and a_c1[0]+lc <= i) or (b_c1 and la <= i+b_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:j+lc<=i+lb), a_c1+a_c2))),
      (lb+i for i in count(a_b2[-1]+1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lc<i), a_c2))),
    ),
    
    chain(
      (la-i for i in a_b3 if (b_c1 and i+b_c1[0]+lc <= 0) or (a_c1 and i+lb <= a_c1[-1]) or any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in takewhile((lambda j:i<=j), a_c1+a_c3))),
      (la-i for i in count(a_b3[-1]-1, -1) if any(j-i in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:i+lb<j), a_c3))),
    ),
    
    chain(
      (lc+i for i in a_c2 if (a_b1 and a_b1[0]+lb <= i) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:j+lb<=i+lc), a_b1+a_b2))),
      (lc+i for i in count(a_c2[-1]+1) if any(i-j in b_c and comp_dup(0,i,j,a,b,c) for j in dropwhile((lambda j:j+lb<i), a_b2))),
    ),
    
    chain(
      (la-i for i in a_c3 if (a_b1 and i+lc <= a_b1[-1]) or any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in takewhile((lambda j:i<=j), a_b1+a_b3))),
      (la-i for i in count(a_c3[-1]-1, -1) if any(i-j in b_c and comp_dup(0,j,i,a,b,c) for j in dropwhile((lambda j:i+lc<j), a_b3))),
    ),
  )
  
  return min(map(next, can))

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

print(min_merge(a,b,c))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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))

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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=None):
  for i in range(1,len(b)):
    if lr!=0:
      m = comp(b[i:], a)
      if m:
        yield  b[:i]+m+a[len(b)-i:], 1
    if lr!=1:
      m = comp(b, a[-len(b)+i:])
      if m:
        yield a[:-len(b)+i]+m+b[-i:], 0
  yield a+b, 0
  yield b+a, 1

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
  l = len(next(merge(d, b, lr)))
  abc = min(abc, l)
print(abc)