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:
a = input()
b = input()
c = input()

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

M = 2000

ab, ac, bc = [], [], []
ab_append = ab.append
ac_append = ac.append
bc_append = bc.append

for _  in range(10000):
    ab_append(0)
    ac_append(0)
    bc_append(0)

for _  in range(10000):
    bc_append(0)

A, B, C = len(a), len(b), len(c)
for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i-j+5000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i-j+5000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i-j+10000] = 1

ans = 3 * M

for i in range(-2*M, 2*M):
    for j in range(-2*M, 2* M):
        if ab[i+5000] == 0 and ac[j+5000] == 0 and bc[j-i+10000] == 0:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R - L)

print(ans)

Submission status: Accepted

Solution code:
K=4000
S=[input()for i in range(3)]
A,B,C=S
a,b,c=len(A),len(B),len(C)
def F(S,T):
 R=[1]*(K*2+1)
 for i in range(-len(T),len(S)):
  for j in range(max(i,0),min(len(S),len(T)+i)):
   if S[j]!=T[j-i]and S[j]!="?"and T[j-i]!="?":
    R[i]=0
    break
 return R
S=F(A,B)
T=F(A,C)
U=F(B,C)
m=K*3
for p in range(-K,K+1):
 if S[p]!=0:
  for q in range(-K,K+1):
   if T[q]!=0 and U[q-p]!=0:
    m=min(m,max(p+b,q+c,a)-min(p,q,0))
print(m)

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=[len(S[t])for t in X];q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import*;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=A,B,C=[len(S[t])for t in X];q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import*;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=map(len,[S[t]for t in X]);q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import*;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=map(len,[S[t]for t in X]);q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in R(3)]
M=[[F(i,j)for j in S]for i in S]
from itertools import *;print(min([Z(i)for i in permutations(R(3))]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);return[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)]+[1]
def Z(X):
 i,j,k=X;A,B,C=map(len,[S[t]for t in X]);q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
T=R(3)
S=[input()for i in T]
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);r=[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)];return r+[1]
def Z(X):
 i,j,k=X;A,B,C=map(len,[S[i]for i in X]);q=1e5
 for l in R(A+1):
  if M[i][j][l]:
   for r in R(l,A+B+1):
    if(B<r-l or M[j][k][r-l])*M[i][k][min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
T=R(3)
S=[input()for i in T]
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);r=[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)];return r+[1]
def Z(X):
 i,j,k=X;U,V,W=M[i][j],M[j][k],M[i][k];A,B,C=map(len,[S[i]for i in X]);q=1e5
 for l in R(A+1):
  if U[l]:
   for r in R(l,A+B+1):
    if(B<r-l or V[r-l])*W[min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
T=R(3)
S=[input()for i in T]
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);r=[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)];return r+[1]
def Z(X):
 i,j,k=X;U,V,W=M[i][j],M[j][k],M[i][k];A,B,C=map(len,[S[i]for i in X]);q=A+B+C
 for l in R(A+1):
  if U[l]:
   for r in R(l,A+B+1):
    if(B<r-l or V[r-l])*W[min(A,r)]:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=R(3)
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
def main():
    a, b, c = [input() for _ in [0]*3]
    p = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)]

    def check(x, y):
        lx, ly = len(x), len(y)
        ans = {lx}
        for i in range(lx):
            for j in range(min(ly, lx-i)):
                if x[i+j] != y[j] and (x[i+j] != "?" and y[j] != "?"):
                    break
            else:
                ans.add(i)
        return ans

    def check2(x, y, z):
        lx, ly, lz = len(x), len(y), len(z)
        ans = lx+ly+lz
        dxy, dyz, dxz = d[(x, y)], d[(y, z)], d[(x, z)]
        for i in dxy:
            ans = min(ans, max(lx, i+ly)+lz)
            for j in dyz:
                if i+j in dxz or i+j >= lx:
                    ans = min(ans, max(lx, i+ly, i+j+lz))
            for j in range(ly, lx-i):
                if i+j in dxz:
                    ans = min(ans, max(lx, i+j+lz))
        return ans

    d = {(x, y): check(x, y) for x, y, z in p}
    print(min([check2(x, y, z) for x, y, z in p]))


main()

Submission status: Accepted

Solution code:
R=range
def F(a,b):A=len(a);r=[all([len(set([a[i+j],b[j],'?']))<3for j in R(min(A-i,len(b)))])for i in R(A)];return r+[1]
def Z(X):
 i,j,k=X;U,V,W=M[i][j],M[j][k],M[i][k];A,B,C=map(len,[S[i]for i in X]);q=A+B+C
 for l in R(A+1):
  if U[l]!=0:
   for r in R(l,A+B+1):
    if (B<r-l or V[r-l]==1) and W[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=R(3)
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
def F(a,b):A=len(a);r=[all([len(set([a[i+j],b[j],'?']))<3for j in range(min(A-i,len(b)))])for i in range(A)];return r+[1]
def Z(X):
 i,j,k=X;U,V,W=M[i][j],M[j][k],M[i][k];A,B,C=map(len,[S[i]for i in X]);q=A+B+C
 for l in range(A+1):
  if U[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or V[r-l]==1) and W[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=range(3)
M=[[F(S[i],S[j])for j in T]for i in T]
from itertools import *;print(min([Z(i)for i in permutations(T)]))

Submission status: Accepted

Solution code:
def F(a,b):
 A=len(a)
 r=[all([len(set([a[i+j],b[j],'?']))<3for j in range(min(A-i,len(b)))])for i in range(A)]
 return r+[1]
def Z(ix):
 i1,i2,i3=ix;ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3];A,B,C=map(len,[S[i]for i in ix]);q=A+B+C
 for l in range(A+1):
  if ab[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=range(3);M=[[F(S[i],S[j])for j in T]for i in T]
print(min([Z(i)for i in[(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]]))

Submission status: Accepted

Solution code:
def F(a,b):
 A=len(a);r=[0]*A
 for i in range(A):
  f=1
  for j in range(min(A-i,len(b))):
   if len(set([a[i+j],b[j],'?']))>2:f=0
  r[i]=f
 return r+[1]
def Z(ix):
 i1,i2,i3=ix;ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3];A,B,C=map(len,[S[i]for i in ix]);q=A+B+C
 for l in range(A+1):
  if ab[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
T=range(3);M=[[F(S[i],S[j])for j in T]for i in T]
print(min([Z(i)for i in[(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]]))

Submission status: Accepted

Solution code:
def F(a,b):
 A=len(a);r=[0]*A
 for i in range(A):
  f=1
  for j in range(min(A-i,len(b))):
   if len(set([a[i+j],b[j],'?']))>2:f=0
  r[i]=f
 return r+[1]
def T(ix):
 i1,i2,i3=ix;ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3];A,B,C=map(len,[S[i]for i in ix]);q=A+B+C
 for l in range(A+1):
  if ab[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
M=[[F(S[i],S[j]) if i!=j else []for j in range(3)]for i in range(3)]
print(min([T(i)for i in [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]]))

Submission status: Accepted

Solution code:
def F(a,b):
 A,B=len(a),len(b)
 r=[0]*A
 for i in range(A):
  f=1
  for j in range(min(A-i,B)):
   if len(set([a[i+j],b[j],'?']))>2:f=0;break
  r[i]=f
 return r+[1]
def T(ix):
 i1,i2,i3=ix;ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3];A,B,C=map(len,[S[i]for i in ix]);q=A+B+C
 for l in range(A+1):
  if ab[l]!=0:
   for r in range(l,A+B+1):
    if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:q=min(q,max(A,l+B,r+C))
 return q
S=[input()for i in'abc']
M=[[F(S[i],S[j]) if i!=j else []for j in range(3)]for i in range(3)]
print(min([T(i)for i in [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]]))

Submission status: Accepted

Solution code:
def chk(a,b):
    A,B=len(a),len(b)
    rt=[0]*A
    for i in range(A):
        f=1
        for j in range(min(A-i,B)):
            if len(set([a[i+j],b[j],'?']))>2:f=0;break
        rt[i]=f
    return rt+[1]

def tri_chk(ix):
    i1,i2,i3=ix
    ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3]
    A,B,C=map(len,[S[i]for i in ix])
    rt=A+B+C
    for l in range(A+1):
        if ab[l]==0:continue
        for r in range(l,A+B+1):
            if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:
                rt=min(rt,max(A,l+B,r+C))
    return rt

S=[input()for i in'abc']
A,B,C=map(len,S)
L=10**5
M=[[chk(S[i],S[j]) if i!=j else []for j in range(3)]for i in range(3)]

for i in [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,1,0),(2,0,1)]:
    L=min(L,tri_chk(i))

print(L)

Submission status: Accepted

Solution code:
from itertools import permutations

def chk(a,b):
    A,B=len(a),len(b)
    rt=[0]*A
    for i in range(A):
        f=1
        for j in range(min(A-i,B)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                f=0;break
        rt[i]=f
    return rt+[1]

def tri_chk(ix):
    i1,i2,i3=ix
    a,b,c=[S[i] for i in ix]
    ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3]
    A,B,C=map(len,(a,b,c))
    rt=A+B+C
    for l in range(A+1):
        if ab[l]==0:
            continue
        for r in range(l,A+B+1):
            if (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:
                alt=max(A,l+B,r+C)
                if alt<rt:
                    rt=alt
    return rt

S=[input()for i in'abc']
A,B,C=map(len,S)
L=10**5
M=[[chk(S[i],S[j]) if i!=j else []for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    L=min(L,tri_chk(i))

print(L)

Submission status: Accepted

Solution code:
from itertools import permutations
def chk(a,b):
    A,B=len(a),len(b)
    rt=[0]*A
    for i in range(A):
        f=1
        for j in range(min(A-i,B)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                f=0;break
        rt[i]=f
    return rt+[1]

def tri_chk(ix):
    i1,i2,i3=ix
    a,b,c=[S[i] for i in ix]
    ab,bc,ac=M[i1][i2],M[i2][i3],M[i1][i3]
    A,B,C=map(len,(a,b,c))
    rt=A+B+C
    for l in range(A+1):
        for r in range(l,A+B+1):
            if ab[l]==1 and (B<r-l or bc[r-l]==1) and ac[min(A,r)]==1:
                        alt=max(A,l+B,r+C)
                        if alt<rt:
                            rt=alt
    return rt

S=[input()for i in'abc']
A,B,C=map(len,S)
L=10**5
M=[[chk(S[i],S[j]) if i!=j else []for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    L=min(L,tri_chk(i))

print(L)

Submission status: Accepted

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

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

def match(x,y):
    if x == y or x == "?" or y == "?":
        return True
    return False
    
ab = [True]*15000
ac = [True]*15000
bc = [True]*15000

for i in range(4000-lb,4000+la):
    for j in range(lb):
        if 4000 <= i+j < 4000+la:
            if not match(a[i+j-4000],b[j]):
                ab[i] = False

for i in range(4000-lc,4000+la):
    for j in range(lc):
        if 4000 <= i+j < 4000+la:
            if not match(a[i+j-4000],c[j]):
                ac[i] = False

for i in range(4000-lc,4000+lb):
    for j in range(lc):
        if 4000 <= i+j < 4000+lb:
            if not match(b[i+j-4000],c[j]):
                bc[i] = False

res = la+lb+lc

for i in range(4000-lb-lc,4000+la+lc+1):
    for j in range(0,4000+la+lb+1):
        if ab[i] and ac[j]:
            if (j-i+4000 >= 15000) or bc[j-i+4000]:
                res = min(res, max(4000+la,i+lb,j+lc)-min(4000,i,j))

print(res)

Submission status: Accepted

Solution code:
from itertools import permutations
def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(l,na+nb+1):
            if ab[l]==1 and (nb<r-l or bc[r-l]==1) and ac[min(na,r)]==1:
                        alt=max(na,l+nb,r+nc)
                        if alt<rt:
                            rt=alt
    return rt
    
a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))
ans=10**5
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Accepted

Solution code:
from itertools import permutations
def check(a,b):
    na=len(a)
    nb=len(b)
    rt=[0]*na
    for i in range(na):
        fl=True
        for j in range(min(na-i,nb)):
            if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                fl=False
                break
        if fl:
            rt[i]=1
    return rt+[1]

def tri_check(idx):
    id1,id2,id3=idx
    a,b,c=[strs[i] for i in idx]
    ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
    na,nb,nc=map(len,(a,b,c))
    rt=na+nb+nc
    al,ar=na,nb
    for l in range(na+1):
        for r in range(nb+1):
            if ab[l]==1 and bc[r]==1 and ac[min(na,l+r)]==1:
                alt=max(na,l+nb,l+r+nc)
                if alt<rt:
                    rt=alt

        if ab[l]==1:
            for r in range(l+nb,na+1):
                if ac[r]==1:
                    alt=max(na,r+nc)
                    if alt<rt:
                        rt=alt
    return rt
    
a=input()
b=input()
c=input()
na,nb,nc=map(len,(a,b,c))
ans=10**5
strs=[a,b,c]
chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]

for i in permutations(range(3)):
    x=tri_check(i)
    ans=min(ans,x)

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True



def PonAC(a,b,c):
    A = len(a)
    B = len(b)
    C = len(c)
     
    def judge(s, t):
    	X = [0] * 200
    	ns, nt = len(s), len(t)
    	for i in range(ns):
    		for j in range(nt):
    			if s[i] != t[j] and s[i] != '?' and t[j] != '?':
    				X[i-j+80] = 1
    	return X
     
    ab = judge(a, b)
    bc = judge(b, c)
    ac = judge(a, c)
    r = A + B + C
    for i in range(-40, 41):
    	for j in range(-40, 41):
    		if (not ab[i+80]) and (not ac[j+80]) and (not bc[j-i+80]):
    			st = min(i, j, 0)
    			en = max(i+B, j+C, A)
    			r = min(en-st, r)
    return r


def ran():
    chs=[-34,-34,0,1,2,3]
    N=len(chs)-1
    mx,Mx=1,6
    x=random.randint(mx,Mx);z=[chs[random.randint(0,N)] for i in ' '*x]
    a=LtoS(z)
    x=random.randint(mx,Mx);z=[chs[random.randint(0,N)] for i in ' '*x]
    b=LtoS(z)
    x=random.randint(mx,Mx);z=[chs[random.randint(0,N)] for i in ' '*x]
    c=LtoS(z)
    return a,b,c

def mys(a,b,c):
    def check(a,b):
        na=len(a)
        nb=len(b)
        rt=[0]*na
        for i in range(na):
            fl=True
            for j in range(min(na-i,nb)):
                if a[i+j]!=b[j] and a[i+j]!='?' and b[j]!='?':
                    fl=False
                    break
            if fl:
                rt[i]=1
        return rt+[1]
    
    def tri_check(idx):
        id1,id2,id3=idx
        a,b,c=[strs[i] for i in idx]
        ab,bc,ac=chMat[id1][id2],chMat[id2][id3],chMat[id1][id3]
        na,nb,nc=map(len,(a,b,c))
        rt=na+nb+nc
        al,ar=na,nb
        for l in range(na+1):
            for r in range(nb+1):
                if ab[l]==1 and bc[r]==1 and (l+r>=na or ac[l+r]==1):
                    #alt=max(na,na+nb+nc-(na-l)-(nb-r))
                    alt=max(na,l+nb,na+nb+nc-(na-l)-(nb-r))
                    if alt<rt:
                        rt=alt
                        al,ar=l,r
            
            if ab[l]==1:
                for r in range(l+nb,na+1):
                    if ac[r]==1:
                        #alt=max(na,na+nb+nc-(na-l)-(nb-r))
                        alt=max(na,r+nc)
                        if alt<rt:
                            rt=alt
                            al,ar=l,r-l
        '''    
        show(a[:al]+b[:ar]+c,' '*(na+nb+nc-len(a[:al]+b[:ar]+c)),rt,(al,ar),ab,bc,ac)
        show(a)
        show(' '*al+b)
        show(' '*(al+ar)+c)
        '''
        return rt
    '''
    a=input()
    b=input()
    c=input()
    '''
    #a,b,c=ran()
    
    na,nb,nc=map(len,(a,b,c))
    ans=10**5
    strs=[a,b,c]
    chMat=[[check(strs[i],strs[j]) if i!=j else [] for j in range(3)]for i in range(3)]
    
    for i in permutations(range(3)):
        x=tri_check(i)
        ans=min(ans,x)
    
    return ans

a=input()
b=input()
c=input()
print(mys(a,b,c))

Submission status: Accepted

Solution code:
a = input()
b = input()
c = input()
 
A = len(a)
B = len(b)
C = len(c)
 
def judge(s, t):
	X = [0] * 20000
	ns, nt = len(s), len(t)
	for i in range(ns):
		for j in range(nt):
			if s[i] != t[j] and s[i] != '?' and t[j] != '?':
				X[i-j+8000] = 1
	return X
 
ab = judge(a, b)
bc = judge(b, c)
ac = judge(a, c)
r = A + B + C
for i in range(-4000, 4001):
	for j in range(-4000, 4001):
		if (not ab[i+8000]) and (not ac[j+8000]) and (not bc[j-i+8000]):
			st = min(i, j, 0)
			en = max(i+B, j+C, A)
			r = min(en-st, r)
print(r)

Submission status: Accepted

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

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

MAX = 2000
MAX2 = 2 * MAX


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


def ok(li1, li2):
    ret = [None] * (2 * MAX2 + 1)
    for i in range(-MAX2, MAX2 + 1):
        if i < 0:
            zp = zip(li1, li2[-i:])
        else:
            zp = zip(li1[i:], li2)
        bl = True
        for e1, e2 in zp:
            if not match(e1, e2):
                bl = False

        ret[i] = bl

    return ret


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

ans = 3 * MAX
for bi in range(-MAX2, MAX2 + 1):
    if ab[bi]:
        for ci in range(-MAX2, MAX2 + 1):
            if ac[ci] and bc[ci-bi]:
                l = min(0, bi, ci)
                r = max(la, bi + lb, ci + lc)
                ans = min(ans, r - l)


print(ans)

Submission status: Accepted

Solution code:
def match(ch1, ch2):
    return ch1 == ch2 or ch1 == '?' or ch2 == '?'

def solve():
    MAXLEN = 2000
    a = raw_input()
    b = raw_input()
    c = raw_input()
    lA = len(a); lB = len(b); lC = len(c)
    MAXLEN = max(lA, lB, lC)
    ab = [True for i in range(10*MAXLEN)]
    ac = [True for i in range(10*MAXLEN)]
    bc = [True for i in range(10*MAXLEN)]
    for i in range(lA):
        for j in range(lB):
            if not match(a[i], b[j]):
                ab[i - j + 5 * MAXLEN] = False
    for i in range(lA):
        for j in range(lC):
            if not match(a[i], c[j]):
                ac[i - j + 5 * MAXLEN] = False
    for i in range(lB):
        for j in range(lC):
            if not match(b[i], c[j]):
                bc[i - j + 5 * MAXLEN] = False
    ret = lA + lB + lC
    for i in range(-2*MAXLEN, 2*MAXLEN+1):
        for j in range(-2*MAXLEN, 2*MAXLEN+1):
            if i < -MAXLEN and j > 0:
                continue
            if i > MAXLEN and j < 0:
                continue
            if j < -MAXLEN and i > 0:
                continue
            if j > MAXLEN and i < 0:
                continue
            if ab[i + 5*MAXLEN] and ac[j + 5*MAXLEN] and bc[j - i + 5*MAXLEN]:
                L = min(0, i, j)
                R = max(lA, lB + i, lC + j)
                ret = min(ret, R - L)
    print ret

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

M = 2000
a = input().strip()
b = input().strip()
c = input().strip()
A = len(a)
B = len(b)
C = len(c)

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

for i in range(A):
    for j in range(B):
        if not match(a[i], b[j]):
            ab[i - j + 10000] = 1
for i in range(A):
    for j in range(C):
        if not match(a[i], c[j]):
            ac[i - j + 10000] = 1
for i in range(B):
    for j in range(C):
        if not match(b[i], c[j]):
            bc[i - j + 10000] = 1

ans = A + B + C
for i in range(-2 * M, 2 * M + 1):
    for j in range(-2 * M, 2 * M + 1):
        if (not ab[i + 10000]) and (not ac[j + 10000]) and (not bc[j - i + 10000]):
            l = min(0, i, j)
            r = max(A, B + i, C + j)
            ans = min(ans, r - l)

print(ans)

Submission status: Accepted

Solution code:
a = list(input())
b = list(input())
c = list(input())
A, B, C = map(len, (a, b, c))
OFFSET = 4000
L = 8001
ab = [True] * L
ac = [True] * L
bc = [True] * L

for i in range(A):
    for j in range(B):
        if a[i] != b[j] and a[i] != '?' and b[j] != '?':
            k = i - j + OFFSET
            ab[i - j + OFFSET] = False  # BをAからi-jずらした時を考える

for i in range(A):
    for j in range(C):
        if a[i] != c[j] and a[i] != '?' and c[j] != '?':
            ac[i - j + OFFSET] = False  # CをAからi-jずらした時を考える

for i in range(B):
    for j in range(C):
        if b[i] != c[j] and b[i] != '?' and c[j] != '?':
            bc[i - j + OFFSET] = False  # CをBからi-jずらした時を考える

ans = float('inf')
for i in range(L):  # Bの左端をずらす
    for j in range(L):  # Cの左端をずらす
        k = j - i + OFFSET
        if k >= L or k < 0:
            continue
        if ab[i] and ac[j] and bc[k]:
            head = min(i, j, OFFSET)
            tail = max(A + OFFSET, B + i, C + j)
            ans = min(ans, tail - head)

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

MX = 2005


def nd(i, j, k, s, d):
    if k >= len(s[i]):
        return True
    return d[i][j][k]


def main():
    s = [''] * 3
    s[0] = input().rstrip('\n')
    s[1] = input().rstrip('\n')
    s[2] = input().rstrip('\n')
    s.sort()
    ans = MX*3
    for ss in itertools.permutations(s):
        d = [[[False for _ in range(MX)] for _ in range(3)] for _ in range(3)]
        for i in range(3):
            for j in range(i+1, 3):
                for k in range(len(ss[i])):
                    check = True
                    for ni in range(k, len(ss[i])):
                        nj = ni-k
                        if nj >= len(ss[j]):
                            break
                        if ss[i][ni] == '?' or ss[j][nj] == '?':
                            continue
                        if ss[i][ni] != ss[j][nj]:
                            check = False
                            break
                    d[i][j][k] = check

        for x in range(MX):
            for y in range(MX):
                if not nd(0, 1, x, ss, d):
                    continue
                if not nd(1, 2, y, ss, d):
                    continue
                if not nd(0, 2, x+y, ss, d):
                    continue
                now = max(len(ss[0]), x+len(ss[1]), x+y+len(ss[2]))
                ans = min(ans, now)
    print(ans)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache
from itertools import permutations
import bisect
INF = 2**62-1

def read_str():
    return input().strip()

def slv(A, B, C):
    @lru_cache(maxsize=None)
    def g(x, y):
        m = []
        for i in range(len(x)):
            for j in range(min(len(y), len(x)-i)):
                if not (x[i+j] == '?' or y[j] == '?' or x[i+j] == y[j]):
                    break
            else:
                m.append(i)
        m.append(len(x))
        return m

    def f(x, y, z):
        lx = len(x)
        ly = len(y)
        lz = len(z)
        ans = lx + ly + lz
        xy = g(x, y)
        yz = g(y, z)
        xz = g(x, z)
        xz_set = set(xz)
        for i in xy:
            for j in yz:
                if i + j < lx and i + j in xz_set:
                    s = max(i + ly, i + j + lz, lx)
                elif i + j < lx and i + len(y) :
                    l = bisect.bisect_left(xz, i+ly)
                    if l >= len(xz):
                        continue
                    k = xz[l]
                    s = max(i + ly, k + len(z), len(x))
                elif  i + j >= lx:
                    s = max(i + ly, i + j + lz, lx)
                else:
                    continue
                ans = min(ans, s)
        return ans

    ans = INF
    for a, b, c in permutations((A, B, C)):
        ans = min(ans, f(a, b, c))

    return ans


def main():
    A = read_str()
    B = read_str()
    C = read_str()
    print(slv(A, B, C))



if __name__ == '__main__':
    main()