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: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def cmp1(a,b):
    l = []
    for i in range(len(a)):
        ok = True
        for j in range(min(len(b),len(a)-i)):
            #ddprint("a {} b {} i {} j {}".format(a,b,i,j))
            #ddprint("aij {} bj {}".format(a[i+j],b[j]))
            if a[i+j]!='?' and b[j]!='?' and a[i+j]!=b[j]:
                ok = False
                break
        if ok:
            l.append(i)
    #ddprint("cmp1 a {} b {} l {}".format(a,b,l))
    return l

def chk3(mn,a,b,c,ab,ac,bc):
    for i in ab:
        v = max(len(a),len(b)+i)+len(c)
        mn = min(mn,v)
        for j in bc:
            if len(a)-i<=j or (j+i) in ac:
                v = max([len(a),len(b)+i,len(c)+i+j])
                mn = min(mn,v)
        for j in ac:
            if len(b)+i<=j:
                v = max(len(a),len(c)+j)
                mn = min(mn,v)

    for i in bc:
        v = max(len(b),len(c)+i)+len(a)
        mn = min(mn,v)
    return mn

def solve(a,b,c):
    ab = cmp1(a,b)
    ac = cmp1(a,c)
    bc = cmp1(b,c)
    ba = cmp1(b,a)
    ca = cmp1(c,a)
    cb = cmp1(c,b)
    mn = len(a)+len(b)+len(c)
    ddprint(mn)
    mn = chk3(mn,a,b,c,ab,ac,bc)
    ddprint(mn)
    mn = chk3(mn,a,c,b,ac,ab,cb)
    ddprint(mn)
    mn = chk3(mn,b,a,c,ba,bc,ac)
    ddprint(mn)
    mn = chk3(mn,b,c,a,bc,ba,ca)
    ddprint(mn)
    mn = chk3(mn,c,a,b,ca,cb,ab)
    ddprint(mn)
    mn = chk3(mn,c,b,a,cb,ca,ba)
    return mn

a = ins()
b = ins()
c = ins()
mn = solve(a,b,c)
print(mn)

Submission status: Accepted

Solution code:
def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

Submission status: Accepted

Solution code:
def main():
  a = input()
  b = input()
  c = input()
  ab = [None]*20000
  ac = [None]*20000
  bc = [None]*20000
  def match(c1,c2):
    return (c1=='?')or(c2=='?')or(c1==c2)

  A = len(a)
  B = len(b)
  C = len(c)
  def solve(d1,d2,n,m,l):
    for i in range(n):
      for j in range(m):
        if not(match(d1[i],d2[j])):
          l[i-j+10000]=True
          continue
    return l
  ab = solve(a,b,A,B,ab)
  ac = solve(a,c,A,C,ac)
  bc = solve(b,c,B,C,bc)
  ans = 6000
  AB = A+B
  AC = A+C
  for i in range(-AC,AC,1):
    for j in range(-AB,AB,1):
      if (not(ab[i+10000]))and(not(ac[j+10000]))and(not(bc[j-i+10000])):
        L = min(0,min(i,j))
        R = max(A,max(B+i,C+j))
        ans = min(ans,R-L)
  print(ans)
  
main()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##
def main():
    S = [rs() for _ in range(3)]
    mi = len(S[0]) + len(S[1]) + len(S[2])
    L = [[set() for i in range(3)] for j in range(3)]
    
    for i in range(3):
        for j in range(3):
            if(i == j): continue
            s = S[i]
            t = S[j]
            for k in range(-len(t), len(s) + 1):
                chk = True
                for l in range(len(s)):
                    ti = l - k
                    if(ti < 0 or ti >= len(t)): continue
                    if(s[l] == t[ti]): continue
                    if(s[l] == '?'): continue
                    if(t[ti] == '?'): continue
                    chk = False
                    break
                if(chk): L[i][j].add(k)
    a = [[0,1,2], [0,2,1], [1,0,2], [1,2,0], [2,0,1], [2,1,0]]
    for ord in a:
        i = ord[0]
        j = ord[1]
        k = ord[2]
        la = 0
        ra = len(S[i])
        for ij in L[i][j]:
            lb = ij
            rb = ij + len(S[j])
            for ik in L[i][k]:
                lc = ik
                rc = ik + len(S[k])
                if lb <= lc and lc < rb:
                    if not ((lc - lb) in L[j][k]): continue
                if lc <= lb and lb < rc:
                    if not ((lb - lc) in L[k][j]): continue
                l = min(la, lb)
                l = min(l, lc)
                r = max(ra, rb)
                r = max(r, rc)
                mi = min(mi, r - l)
    
    print(mi)
                


if __name__ == "__main__":
    main()

Submission status: Accepted

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]=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]=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]=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] and flag_ac[left_c-left_a] 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: Accepted

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: Accepted

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


def check(s, t):
    M = 10 ** 4
    ANS = [1] * (2 * M)
    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 + M] = 0
    return ANS


def solve(a, b, c):
    M = 10 ** 4
    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 + M] and AC[j + M] and BC[j - i + M]:
                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: Accepted

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


def check(s, t):
    ANS = [1] * (10 ** 5)
    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 + 50000] = 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 + 50000] and AC[j + 50000] and BC[j - i + 50000]:
                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: Accepted

Solution code:
a=input()
len_a=len(a)
b=input()
len_b=len(b)
c=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[j]!='?':
      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[j]!='?':
      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[j]!='?':
      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: Accepted

Solution code:
import sys
import itertools
 
A = list(sys.stdin.readline().strip())
B = list(sys.stdin.readline().strip())
C = list(sys.stdin.readline().strip())
 
def can_match(x,y):
    return x == '?' or y == '?' or x == y

M = 2020
def solve(A,B,C,LA,LB,LC):
    B_from_A = [True] * (M+1)
    for i in range(M+1):
        B_from_A[i] = all(can_match(x,y) for x, y in zip(A[i:], B))
    C_from_A = [True] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x, y in zip(A[i:], C))
    C_from_B = [True] * (M+1)
    for i in range(M+1):
        C_from_B[i] = all(can_match(x,y) for x, y in zip(B[i:], C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(M):
            if not C_from_B[j]:
                continue
            if not C_from_A[i+j]:
                continue
            yield max(LA, LB+i, LC+i+j)
            break
 
answer = float("inf")
for A,B,C in itertools.permutations([A, B, C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A, B, C, LA, LB, LC))
    answer = min(answer, x)
print(answer)

Submission status: Accepted

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[j]!='?':
      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[j]!='?':
      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[j]!='?':
      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: Accepted

Solution code:
import itertools

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

ab=[0]*100000
ac=[0]*100000
bc=[0]*100000

lena=len(a)
lenb=len(b)
lenc=len(c)

def match(c1,c2):
    return c1==c2 or c1=='?' or c2=='?'

for i in range(lena):
    for j in range(lenb):
        if match(a[i],b[j])==False:
            ab[i-j+50000]=1

for i in range(lena):
    for j in range(lenc):
        if match(a[i],c[j])==False:
            ac[i-j+50000]=1

for i in range(lenb):
    for j in range(lenc):
        if match(b[i],c[j])==False:
            bc[i-j+50000]=1
ans=10000
for i in range(-4000,4001):
    for j in range(-4000,4001):
        if ab[i+50000]==0 and ac[j+50000]==0 and bc[j-i+50000]==0:
            left=min(0,i,j)
            right=max(lena,i+lenb,j+lenc)
            ans=min(ans,right-left)

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return input().rstrip()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("inf")

#solve
def solve():
    a = S()
    b = S()
    c = S()
    def f(a, b, c):
        lena, lenb, lenc = len(a), len(b), len(c)
        dpab = [inf] * (lena + 1)
        dpbc = [inf] * (lenb + 1)
        dpac = [inf] * (lena + 1)
        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenb):
                if l == lena:
                    break
                if a[l] == b[r] or a[l] == "?" or b[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpab[tl] = max(tl + lenb, lena)

        for l in range(lenb + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lenb:
                    break
                if b[l] == c[r] or b[l] == "?" or c[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpbc[tl] = max(tl + lenc, lenb)

        for l in range(lena + 1):
            f = 0
            tl = l
            for r in range(lenc):
                if l == lena:
                    break
                if a[l] == c[r] or a[l] == "?" or c[r] == "?":
                    l += 1
                else:
                    f = 1
                    break
            if f:
                continue
            dpac[tl] = max(tl + lenc, lena)

        res = lena + lenb + lenc
        for l in range(lena + 1):
            for r in range(lenb + 1):
                lr = l + r
                if dpab[l] != inf and dpbc[r] != inf:
                    if lr > lena:
                        res = min(l + dpbc[r], res)
                    else:
                        if dpac[lr] != inf:
                            if dpbc[r] == lenb:
                                res = min(res, dpab[l])
                            else:
                                res = min(res, dpac[lr])
            for r in range(l + lenb, lena + 1):
                if dpab[l] == lena:
                    if dpac[r] != inf:
                        res = min(res, dpac[r])
        return res

    ans = len(a) + len(b) + len(c)
    ans = min(ans, f(a, b, c))
    ans = min(ans, f(a, c, b))
    ans = min(ans, f(b, a, c))
    ans = min(ans, f(b, c, a))
    ans = min(ans, f(c, b, a))
    ans = min(ans, f(c, a, b))
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
maxn = 2000 * 4 + 3
maxnh = maxn // 2
 
def check(s, t, d):
    for i in range(max(0, d), min(len(s), len(t) + d)):
        if s[i] != '?' and t[i - d] != '?' and s[i] != t[i - d]:
            return False
    return True
 
def ca(s, t):
    res = [True] * maxn
    for i in range(-len(t), len(s) + 1):
        res[i + maxnh] = check(s, t, i)
    return res
 
a, b, c = (input() for _ in range(3))
ans = sum(map(len, (a, b, c)))
ab, bc, ac = ca(a, b), ca(b, c), ca(a, c)
 
for i in range(maxn):
    if not ab[i]:
        continue
    for j in range(maxn):
        if not bc[j]:
            continue
        if (0 <= i + j - maxnh < maxn) and not ac[i + j - maxnh]:
            continue
        ans = min(ans, max(len(a), len(b) + i - maxnh, len(c) + i + j - maxnh * 2) - min(0, i - maxnh, i + j - maxnh * 2))
 
print(ans)

Submission status: Accepted

Solution code:
a = input()
b = input()
c = input()
la, lb, lc = len(a), len(b), len(c)

M = 4000
M2 = 20000
M2offset = 10000


def canInserts(n, m):
    r = [True]*M2
    for i in range(len(n)):
        for j in range(len(m)):
            if n[i] != m[j] and n[i] != '?' and m[j] != '?':
                r[i-j+M2offset] = False
    return r


ab = canInserts(a, b)
ac = canInserts(a, c)
bc = canInserts(b, c)

ans = M2
for bi in range(-M, M+1):
    if not ab[bi+M2offset]:
        continue
    for ci in range(-M, M+1):
        if ac[ci+M2offset] and bc[ci-bi+M2offset]:
            l = min(0, bi, ci)
            r = max(la, bi+lb, ci+lc)
            t = r-l
            if ans > t:
                ans = t
print(ans)

Submission status: Accepted

Solution code:
import sys

def match(a,b):
    return a == '?' or b== '?' or a == b


def solve(a, b, c):
    a = list(a)
    b = list(b)
    c = list(c)
    ab = [False] * 100000
    ac = [False] * 100000
    bc = [False] * 100000
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i],b[j]):
                ab[i-j+50000] = True
    for i in range(len(b)):
        for j in range(len(c)):
            if not match(b[i],c[j]):
                bc[i-j+50000] = True
    for i in range(len(a)):
        for j in range(len(c)):
            if not match(a[i],c[j]):
                ac[i-j+50000] = True
    M = max(len(a),len(b),len(c))
    ans = M*3
    for i in range(-M*2,M*2+1):
        for j in range(-M*2,M*2+1):
            if not ab[i + 50000] and not ac[j + 50000] and not bc[j-i + 50000]:
                L = min(i,j,0)
                R = max(len(a),len(b)+i,len(c)+j)
                ans = min(ans,R-L)
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Accepted

Solution code:
a = input()
b = input()
c = input()

def match(c1, c2):
    return c1 == c2 or c1 == "?" or c2 == "?"

def check(x, y, l_m=2000):
    xy = [0] * (l_m * 8 + 1)
    mid = l_m * 4
    for i in range(len(x)):
        for j in range(len(y)):
            if not match(x[i], y[j]):
                xy[i - j + mid] = 1
    return xy

l_a = len(a)
l_b = len(b)
l_c = len(c)

ab = check(a, b)
ac = check(a, c)
bc = check(b, c)

l_m = 2000
mid = l_m * 4

ans = 3 * l_m
for i in range(-2 * l_m, 2 * l_m + 1):
    if ab[i + mid]:
        continue
    for j in range(-2 * l_m, 2 * l_m + 1):
        if ac[j + mid] or bc[j - i + mid]:
            continue

        lb = min(0, min(i, j))
        ub = max(l_a, max(l_b + i, l_c + j))
        ans = min(ans, ub - lb)

print(ans)

Submission status: Accepted

Solution code:
a=input()
a_l=len(a)
b=input()
b_l=len(b)
c=input()
c_l=len(c)
def check(s1,s2):
    l1=len(s1)
    l2=len(s2)
    ret=[0]*(l1+l2-1)
    for i in range(l1+l2-1):
        flag=True
        if i-l2+1<0 and i<=l1-1:
            for j in range(i+1):
                if s1[j]!="?" and s2[l2-i+j-1]!="?" and s1[j]!=s2[l2-i+j-1]:
                    flag=False
                    break
        elif i-l2+1<0 and i>l1-1:
            for j in range(l1):
                if s1[j]!="?" and s2[l2-i+j-1]!="?" and s1[j]!=s2[l2-i+j-1]:
                    flag=False
                    break
        elif i-l2+1>=0 and i<=l1-1:
            for j in range(l2):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        else:
            for j in range(l1+l2-i-1):
                if s1[i-l2+j+1]!="?" and s2[j]!="?" and s1[i-l2+j+1]!=s2[j]:
                    flag=False
                    break
        ret[i]=flag
    return ret
ab=check(a,b)
ab_l=len(ab)
ac=check(a,c)
ac_l=len(ac)
bc=check(b,c)
bc_l=len(bc)
ans=a_l+b_l+c_l
for i in range(-2000,ab_l+2000):
    if i<0 or i>=ab_l or ab[i]:
        for j in range(-2000,ac_l+2000):
            if j<0 or j>=ac_l or ac[j]:
                if j-i+b_l-1<0 or j-i+b_l-1>=bc_l or bc[j-i+b_l-1]:
                    l=max(a_l-1,i,j)-min(0,i-b_l+1,j-c_l+1)+1
                    ans=min(ans,l)
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

A,B,C = read().decode().split()

A = list(A)
B = list(B)
C = list(C)

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

M = 2020

def solve(A,B,C,LA,LB,LC):
    B_from_A = [True] * (M+1)
    for i in range(M+1):
        B_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],B))
    C_from_A = [True] * (M+M+1)
    for i in range(M+M+1):
        C_from_A[i] = all(can_match(x,y) for x,y in zip(A[i:],C))
    C_from_B = [True] * (M+1)
    for i in range(M+1):
        C_from_B[i] = all(can_match(x,y) for x,y in zip(B[i:],C))
    for i in range(M):
        if not B_from_A[i]:
            continue
        for j in range(M):
            if not C_from_B[j]:
                continue
            if not C_from_A[i+j]:
                continue
            yield max(LA, LB+i, LC+i+j)
            break

answer = 10 ** 9
for A,B,C in itertools.permutations([A,B,C]):
    LA = len(A)
    LB = len(B)
    LC = len(C)
    x = min(solve(A,B,C,LA,LB,LC))
    if answer > x:
        answer = x
print(answer)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# MOD = 998244353


A, B, C = [sys.stdin.buffer.readline().decode().rstrip() for _ in range(3)]
A = list(map(ord, A))
B = list(map(ord, B))
C = list(map(ord, C))

memo = {}
Q = ord('?')


def get_ok_idx(A, B):
    key = str(A) + str(B)
    if key in memo:
        return memo[key]
    ret = []
    for i in range(len(A) + 1):
        for a, b in zip(A[i:], B):
            if a != b and a != Q and b != Q:
                break
        else:
            ret.append(i)
    memo[key] = ret
    return ret


# A = np.array(A, dtype=int)
# B = np.array(B, dtype=int)
# C = np.array(C, dtype=int)

def solve(A, B, C):
    ok_ab = get_ok_idx(A, B)
    ok_bc = get_ok_idx(B, C)
    ok_cb = get_ok_idx(C, B)
    ok_ac = get_ok_idx(A, C)

    ok_ab_flags = [False] * (len(A) + 1)
    ok_bc_flags = [False] * (len(B) + 1)
    ok_cb_flags = [False] * (len(C) + 1)
    ok_ac_flags = [False] * (len(A) + 1)
    for i in ok_ab:
        ok_ab_flags[i] = True
    for i in ok_bc:
        ok_bc_flags[i] = True
    for i in ok_cb:
        ok_cb_flags[i] = True
    for i in ok_ac:
        ok_ac_flags[i] = True

    ret = INF
    for ab, bc in itertools.product(ok_ab, ok_bc):
        if ab + bc >= len(A) or ok_ac_flags[ab + bc]:
            ret = min(ret, max(len(A), ab + len(B), ab + bc + len(C)))
    for ac, bc in itertools.product(ok_ac, ok_bc):
        if ac - bc < 0:
            continue
        if ac - bc >= len(A) or ok_ab_flags[ac - bc]:
            ret = min(ret, max(len(A), ac - bc + len(B), ac + len(C)))
    for ab, ac in itertools.product(ok_ab, ok_ac):
        if ab < ac and (ac - ab >= len(B) or ok_bc_flags[ac - ab]):
            ret = min(ret, max(len(A), ab + len(B), ac + len(C)))
        elif ac < ab and (ab - ac >= len(C) or ok_cb_flags[ab - ac]):
            ret = min(ret, max(len(A), ab + len(B), ac + len(C)))
    return ret


ans = len(A) + len(B) + len(C)
ans = min(ans, solve(A, B, C))
ans = min(ans, solve(A, C, B))
ans = min(ans, solve(B, A, C))
ans = min(ans, solve(B, C, A))
ans = min(ans, solve(C, A, B))
ans = min(ans, solve(C, B, A))
print(ans)

Submission status: Accepted

Solution code:
a = input()
b = input()
c = input()
La = len(a)
Lb = len(b)
Lc = len(c)

def func(a, b):
    ret = set()
    for i in range(-len(b)+1, len(a)):
        ok = True
        for j in range(max(0, i), min(len(a), len(b)+i)):
            if a[j] != '?' and b[j-i] != '?' and a[j] != b[j-i]:
                ok = False
                break
        if ok:
            ret.add(i)
    return ret

L1 = func(a, b)
L2 = func(a, c)
L3 = func(b, c)
L1.add(-Lb)
L1.add(La)
L2.add(-Lc)
L2.add(La)
L3.add(-Lc)
L3.add(Lb)
ans = 10000
for i in L1:
    for j in L2:
        if j - i in L3 or j - i <= -Lc or j - i >= Lb:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    for k in L3:
        j = i + k
        if j >= La or j <= -Lc:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
for j in L2:
    for k in L3:
        i = j - k
        if i >= La or i <= -Lb:
            lo = min(0, i, j)
            hi = max(len(a), i+len(b), j+len(c))
            ans = min(ans, hi-lo)
    
print(ans)

Submission status: Accepted

Solution code:
import sys

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()))

ques = ord('?')

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):
  l = [0]*len(t)
  for i in range(len(t)):
    j = 0
    while j < len(s) and i+j < len(t) and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
      j += 1
    l[i] = j
  return l

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])
            # print(i,j,g[i][j])
ans = sum(len(x) for x in l)
for i in range(3):
    for j in range(3):
        if i == j: continue
        k = 3-i-j
        li = [ii for ii in range(len(l[i])) if g[j][i][ii] >= min(len(l[i]) - ii, len(l[j]))]
        lj = [ii for ii in range(len(l[j])) if g[k][j][ii] >= min(len(l[j]) - ii, len(l[k]))]
        lk = [ii for ii in range(len(l[i])) if g[k][i][ii] >= min(len(l[i]) - ii, len(l[k]))]
        if li:
            c = max(len(l[i]), min(li) + len(l[j])) + len(l[k])
            if ans > c: ans = c
        for ii in li:
            for jj in lj:
                kk = ii + jj
                if kk >= len(l[i]) or g[k][i][kk] >= min(len(l[i]) - kk, len(l[k])):
                    c = max(len(l[i]), ii + len(l[j]), kk + len(l[k]))
                    if ans > c: ans = c
        for ii in li:
            for kk in lk:
                if kk < ii + len(l[j]): continue
                c = max(len(l[i]), ii + len(l[j]), kk + len(l[k]))
                if ans > c: ans = c
print(ans)

Submission status: Accepted

Solution code:
a = input()
b = input()
c = input()

la = len(a)
lb = len(b)
lc = len(c)

AB = [False]*la
AC = [False]*la
BA = [False]*lb
BC = [False]*lb
CA = [False]*lc
CB = [False]*lc
for i in range(la):
    for s,t in zip(a[i:],b):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        AB[i] = True
for i in range(la):
    for s,t in zip(a[i:],c):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        AC[i] = True
for i in range(lb):
    for s,t in zip(b[i:],a):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        BA[i] = True
for i in range(lb):
    for s,t in zip(b[i:],c):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        BC[i] = True
for i in range(lc):
    for s,t in zip(c[i:],a):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        CA[i] = True
for i in range(lc):
    for s,t in zip(c[i:],b):
        if not(s=='?' or t=='?' or s==t):
            break
    else:
        CB[i] = True

ans = la+lb+lc
for i in range(-(lb+lc),la+max(lb,lc)+1):
    if 0<=i<la:
        ab = AB[i]
    elif -lb<i<0:
        ab = BA[-i]
    else:
        ab = True
    if not ab: continue
    l = min(0,i)
    r = max(la,i+lb)
    if ans <= r-l : continue
    for j in range(-(lb+lc),la+max(lb,lc)+1):
        
        
        if 0<=j<la:
            ac = AC[j]
        elif -lc<j<0:
            ac = CA[-j]
        else:
            ac = True
            
        k = j-i
        if 0<=k<lb:
            bc = BC[k]
        elif -lc<k<0:
            bc = CB[-k]
        else:
            bc = True
        
        if ab and ac and bc:
            l = min(0,i,j)
            r = max(la,i+lb,j+lc)
            ans = min(ans,r-l)
print(ans)