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.

Solution (Python):
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()

Solution (Python):

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


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


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
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):
        N = len(x) + len(y) + len(z)
        ans = N
        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 < len(x) and i + j in xz_set:
                    s = max(i + len(y), i + j + len(z), len(x))
                elif i + j < len(x) and i + len(y) :
                    l = bisect.bisect_left(xz, i+len(y))
                    if l >= len(xz):
                        continue
                    k = xz[l]
                    
                    s = max(i + len(y), k + len(z), len(x))
                elif  i + j >= len(x):
                    s = max(i + len(y), i + j + len(z), len(x))
                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 ref(A, B, C):
    def f(x, y):
        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:
                if len(y) > len(x)-i:
                    s = x + y[len(x)-i:]
                    s = list(s)
                    for j in range(len(x)-i):
                        if (x[i+j] == '?' and y[j] != '?'):
                            s[i+j] = y[j]
                    yield ''.join(s)
                else:
                    s = list(x)
                    for j in range(len(y)):
                        if (x[i+j] == '?' and y[j] != '?'):
                            s[i+j] = y[j]
                    yield ''.join(s)
        yield x + y
    ans = INF
    for x, y, z in permutations((A, B, C)):
        
        for xy in f(x, y):
            for xyz in f(xy, z):
                
                ans = min(ans, len(xyz))
    return ans

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


    
    
    
    
    
    
    
    
    



    
    

    
    
    
    
    
    
    
    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
def match(s, t, ls, lt, i):
    return all(s[i + j] == '?' or t[j] == '?' or s[i + j] == t[j] for j in range(min(ls - i, lt)))


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

ab = [match(a, b, la, lb, i) for i in range(0, la)] + [True] * 8000
ac = [match(a, c, la, lc, i) for i in range(0, la)] + [True] * 8000
bc = [match(b, c, lb, lc, i) for i in range(0, lb)] + [True] * 8000
ba = [match(b, a, lb, la, i) for i in range(1, lb)] + [True] * 8000
ca = [match(c, a, lc, la, i) for i in range(1, lc)] + [True] * 8000
cb = [match(c, b, lc, lb, i) for i in range(1, lc)] + [True] * 8000
ab.extend(reversed(ba))
ac.extend(reversed(ca))
bc.extend(reversed(cb))

ans = la + lb + lc

for db in range(-lb - lc, la + lc + 1):
    ab_ok = ab[db]
    if not ab_ok:
        continue
    for dc in range(-lb - lc, la + lb + 1):
        ac_ok = ac[dc]
        bc_ok = bc[dc - db]
        if ac_ok and bc_ok:
            ans = min(ans, max(la, db + lb, dc + lc) - min(0, db, dc))

print(ans)

Solution (Python):
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    def same(x,y):
        xn,yn=len(x),len(y)
        
        res = [True] * 4005
        for i in range(xn):
            for c0, c1 in zip(x[i:], y):
                if c0 != q and c1 != q and c0 != c1:
                    res[i] = False
                    break
        return res

    q=ord("?")
    ss=[[ord(c) for c in SI()] for _ in range(3)]
    
    eq=[[0]*3 for _ in range(3)]
    for i in range(3):
        for j in range(3):
            if i==j:continue
            eq[i][j]=same(ss[i],ss[j])
    
    ans=sum(len(ss[i]) for i in range(3))
    for si,sj,sk in permutations(range(3)):
        for i in range(len(ss[si])+1):
            for j in range(max(len(ss[sj]),len(ss[si])-i)+1):
                if eq[si][sj][i] and eq[sj][sk][j] and eq[si][sk][i+j]:
                    cur=max(len(ss[si]),len(ss[sj])+i,len(ss[sk])+i+j)
                    ans=min(ans,cur)
    print(ans)

main()

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



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

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

def prefix_match_len(x,y):
    len_list = []
    n = len(x)
    m = len(y)
    for i in range(n):
        match = 0
        for j in range(i,min(i+m,n)):
            if is_match(x[j],y[j-i]):
                match += 1
            else:
                break
        len_list.append(match)
    return len_list

def concat(x,y,xy):
    index_list = []
    n = len(x)
    m = len(y)
    for i in range(n):
        if xy[i] == min(n-i,m):
            index_list.append(i)
    index_list.append(n)
    return index_list

def concat2(x,y,z,xz,yz,zy,index_list):
    n1 = len(x)
    n2 = len(y)
    m = len(z)
    candidate = []
    for i in index_list:
        flag = False
        for j in range(max(n1,n2+i)):
            if j <= n1-1:
                if xz[j] != min(n1-j,m):
                    continue
            if j >= i:
                if n2-j+i >= 1 and yz[j-i] != min(n2-j+i,m):
                    continue
            else:
                if m-i+j >= 1 and zy[i-j] != min(m-i+j,n2):
                    continue
            flag = True
            candidate.append(max(n1,n2+i,j+m))
            break
        if not flag:
            candidate.append(max(n1,n2+i)+m)
    return min(candidate)

ab = prefix_match_len(a,b)
ac = prefix_match_len(a,c)
ba = prefix_match_len(b,a)
bc = prefix_match_len(b,c)
ca = prefix_match_len(c,a)
cb = prefix_match_len(c,b)

index_list = concat(a,b,ab)
ret1 = concat2(a,b,c,ac,bc,cb,index_list)
index_list = concat(a,c,ac)
ret2 = concat2(a,c,b,ab,cb,bc,index_list)
index_list = concat(b,a,ba)
ret3 = concat2(b,a,c,bc,ac,ca,index_list)
index_list = concat(b,c,bc)
ret4 = concat2(b,c,a,ba,ca,ac,index_list)
index_list = concat(c,a,ca)
ret5 = concat2(c,a,b,cb,ab,ba,index_list)
index_list = concat(c,b,cb)
ret6 = concat2(c,b,a,ca,ba,ab,index_list)

print(min(ret1,ret2,ret3,ret4,ret5,ret6))

Solution (Python):

A = input()
B = input()
C = input()

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

la = len(A)
lb  =len(B)
lc = len(C)

ml = max(la, lb, lc)


ab = [False for _ in range(ml * 4 + 1)]
ac = [False for _ in range(ml * 4 + 1)]
bc = [False for _ in range(ml * 4 + 1)]

"""
下の２重forで(i,j) = (0,0)と(1,1)で配列のindexが同じになってしまうが、AとBの０文字目どうし、1文字目どうしを比べるのは、
同じところから先頭が始まっている場合なので、あるずれの配置について、全文字比較していることになる
i=0,j=2とかだとBのほうが左にある場合で、i=3,j=0だとAが左にある場合

ab[i - j]のindexに+2mlして、-2ml ~ 2ml 感を出したい気持ちがあるが、意味がないのでしない
"""


def main():

    for i in range(la):
        for j in range(lb):
            
            if ab[i - j]:
                continue
            
            if not match(A[i], B[j]):
                ab[i - j] = True


    for i in range(la):
        for j in range(lc):
            
            if ac[i - j]:
                continue
            
            if not match(A[i], C[j]):
                ac[i - j] = True

    for i in range(lb):
        for j in range(lc):
            
            if bc[i - j]:
                continue
            
            if not match(B[i], C[j]):
                bc[i - j] = True       

    ans = la + lb + lc
    
    for i in range(-2*ml, 2*ml+1):
        
        if ab[i]:
            continue
        
        for j in range(-2*ml, 2*ml+1):
            if ac[j]:
                continue
            
            
            
            if bc[j - i]:
                continue

            
            l = min(0, i, j)
            
            r = max(0 + la, i + lb, j + lc)
            ans = min(ans, r - l)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    def check(S, T):
        assert len(S) == len(T)
        for s, t in zip(S, T):
            if s == t or s == '?' or t == '?':
                continue
            return 0
        return 1

    A = input().rstrip('\n')
    B = input().rstrip('\n')
    C = input().rstrip('\n')
    la = len(A)
    lb = len(B)
    lc = len(C)
    AB = [1] * 10010
    BC = [1] * 10010
    AC = [1] * 10010
    for i in range(-lb, la+1):
        AB[i] = check(A[max(0, i):min(la, i+lb)], B[max(0, -i):min(lb, la-i)])
    for i in range(-lc, lb+1):
        BC[i] = check(B[max(0, i):min(lb, i+lc)], C[max(0, -i):min(lc, lb-i)])
    for i in range(-lc, la+1):
        AC[i] = check(A[max(0, i):min(la, i+lc)], C[max(0, -i):min(lc, la-i)])

    ans = la+lb+lc
    for i in range(-lb-lc-3, la+lc+3):
        if not AB[i]:
            continue
        for j in range(-lb-lc-3, la+lb+3):
            if BC[j-i] and AC[j]:
                l = min(0, i, j)
                r = max(la, lb+i, lc+j)
                
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import permutations, product
import sys

def input(): return sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)

MX = 2005
d = [[[0]*MX for _ in range(3)] for _ in range(3)]


s = [input() for _ in range(3)]
s.sort()


ans = MX*3
for sss in permutations(s):
    
    for i, j in product(range(3), repeat=2):
        for k in range(len(sss[i])):
            if i >= j: continue
            
            ok = True
            for ni in range(k, len(sss[i])):
                nj = ni - k
                if nj >= len(sss[j]): break
                if sss[i][ni] == '?' or sss[j][nj] == '?': continue
                if sss[i][ni] != sss[j][nj]: ok = False
            d[i][j][k] = ok
    def f(i, j, k):
        if k >= len(sss[i]):
            return True
        return d[i][j][k]
    
    for x, y in product(range(MX), repeat=2):
        if f(0,1,x) == False: continue
        if f(1,2,y) == False: continue
        if f(0,2,x+y) == False: continue
        now = 0
        now = max(now, len(sss[0]))
        now = max(now, x+len(sss[1]))
        now = max(now, x+y+len(sss[2]))
        ans = min(ans, now)
print(ans)

Solution (Python):


"""
左端の順番を固定して考えた.(A,B,Cの順とする)
n : Aの長さ, m : Bの長さ, l : Cの長さ
AB : Aを固定した時のBが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
AC : Aを固定した時のCが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
BC : Bを固定した時のCが一致する先頭位置
　　⇒ Bの先頭からBの末尾+1の位置までm+1箇所考える + nがmより大きい場合はBとCが離れているかもしれないので, Aの末尾+1まで考える
　　⇒ Bの先頭からmax(n,m)+1の位置まで考える
"""

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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n+1), [True]*(n+1), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(max(n,m)+1):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)

    res = n + m + l
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n:
                    res = min(res, max(n, i + m, i + j + l))
                elif AC[i + j]:
                    res = min(res, max(n, i + m, i + j + l))
    return res

def main():
    a = input()
    b = input()
    c = input()
    ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


"""
左端の順番を固定して考えた.(A,B,Cの順とする)
n : Aの長さ, m : Bの長さ, l : Cの長さ
AB : Aを固定した時のBが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
AC : Aを固定した時のCが一致する先頭位置
    ⇒ Aの先頭からAの末尾+1の位置までn+1箇所考える
BC : Bを固定した時のCが一致する先頭位置
　　⇒ Bの先頭からBの末尾+1の位置までm+1箇所考える + nがmより大きい場合はBとCが離れているかもしれないので, Aの末尾+1まで考える
"""

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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n+1), [True]*(n+1), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

    res = n + m + l
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n:
                    res = min(res, max(n, i + m, i + j + l))
                elif AC[i + j]:
                    res = min(res, max(n, i + m, i + j + l))
    return res

def main():
    a = input()
    b = input()
    c = input()
    ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
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])
            
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]))]

        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)

Solution (Python):
import sys
input = sys.stdin.readline

A = input().rstrip()
B = input().rstrip()
C = input().rstrip()

def check(P1, P2, P3):
    L1 = len(P1)
    L2 = len(P2)
    L3 = len(P3)
    L = sum([L1, L2, L3])*2+3

    P12 = [True]*L
    for i2 in range(-L2, L1+1):
        for l in range(max(i2, 0), min(i2+L2, L1)):
            if P1[l] != "?" and P2[l-i2] != "?" and P1[l] != P2[l-i2]:
                P12[i2] = False
                break
    
    P13 = [True]*L
    for i3 in range(-L3, L1+1):
        for l in range(max(i3, 0), min(i3+L3, L1)):
            if P1[l] != "?" and P3[l-i3] != "?" and P1[l] != P3[l-i3]:
                P13[i3] = False
                break
    
    P23 = [True]*L
    for i3 in range(-L3, L2+1):
        for l in range(max(i3, 0), min(i3+L3, L2)):
            if P2[l] != "?" and P3[l-i3] != "?" and P2[l] != P3[l-i3]:
                P23[i3] = False
                break

    ans = L1 + L2 + L3
    for i2 in range(-L2, L1+1):
        for i3 in range(-L3, L1+1):
            if P12[i2] and P13[i3] and P23[i3-i2]:
                ans = min(ans, max([L1, L2+i2, L3+i3]) - min([0, i2, i3]))
    return ans



print(min([check(A, B, C), check(B, A, C), check(C, A, B)]))

Solution (Python):


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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n+1), [True]*(n+1), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

    res = n + m + l
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n:
                    res = min(res, max(n, i + m, i + j + l))
                elif AC[i + j]:
                    res = min(res, max(n, i + m, i + j + l))
    return res

def main():
    a = input()
    b = input()
    c = input()
    ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


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

def solve(A, B, C):
    n, m, l = len(A), len(B), len(C)
    AB, AC, BC = [True]*(n+1), [True]*(n+1), []
    for i in range(n):
        for j in range(m):
            if i + j >= n:
                continue
            if not compare(A[i + j], B[j]):
                AB[i] = False
                break
    
    for i in range(n):
        for j in range(l):
            if i + j >= n:
                continue
            if not compare(A[i + j], C[j]):
                AC[i] = False
                break

    for i in range(n):
        for j in range(l):
            if i + j >= m:
                continue
            if compare(B[i + j], C[j]):
                continue
            break
        else:
            BC.append(i)
    for i in range(max(0,n-m)):
        BC.append(m+i)

    res = n + m + l
    for i in range(n+1):
        if AB[i]:
            for j in BC:
                if i + j >= n:
                    res = min(res, max(i + m, i + j + l))
                elif AC[i + j]:
                    res = min(res, max(n, i + m, i + j + l))
    return res

def main():
    a = input()
    b = input()
    c = input()
    ans = min(solve(a,b,c),solve(a,c,b),solve(b,a,c),solve(b,c,a),solve(c,a,b),solve(c,b,a))
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):


def solve_panasonic2020_e():
    def unmatched(c1: str, c2: str) -> bool:
        """c1,c2がマッチしない"""
        return not (c1 == '?' or c2 == '?' or c1 == c2)

    A = input()
    B = input()
    C = input()

    MX = max(map(len, [A, B, C]))

    
    
    
    
    
    ab = [False] * (MX * 4 + 1)
    ac = [False] * (MX * 4 + 1)
    bc = [False] * (MX * 4 + 1)

    for i, a in enumerate(A):
        for j, b in enumerate(B):
            ab[i - j] |= unmatched(a, b)

    for i, a in enumerate(A):
        for j, c in enumerate(C):
            ac[i - j] |= unmatched(a, c)

    for i, b in enumerate(B):
        for j, c in enumerate(C):
            bc[i - j] |= unmatched(b, c)

    
    ans = sum(map(len, [A, B, C]))
    for i in range(-MX * 2, MX * 2 + 1):  
        if ab[i]: continue
        for j in range(-MX * 2, MX * 2 + 1):  
            if ac[j]: continue
            if bc[j - i]: continue
            
            
            
            
            
            

            
            L = min(0, i, j)
            R = max(len(A), i + len(B), j + len(C))
            ans = min(ans, R - L)

    print(ans)
    return


if __name__ == '__main__':
    solve_panasonic2020_e()

Solution (Python):
a = input().strip()
b = input().strip()
c = input().strip()
kk = 2000
K = kk*2
na, nb, nc = len(a), len(b), len(c)
def ll(s, t):
    X = [0] * 100000
    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+2*K] = 1
    return X

ab = ll(a, b)
bc = ll(b, c)
ac = ll(a, c)
r = na+nb+nc
for i in range(-K, K+1):
    for j in range(-K, K+1):
        if (not ab[i+2*K]) and (not ac[j+2*K]) and (not bc[j-i+2*K]):
            st = min(i, j, 0)
            en = max(i+nb, j+nc, na)
            r = min(en-st, r)
print(r)

Solution (Python):


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

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

M = max(A, B, C)
cons = 6*M
a_not_match_b = [False] * 2 * cons
b_not_match_c = [False] * 2 * cons
a_not_match_c = [False] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)): 
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = True 
    return l

a_not_match_b = fill_match_list(a, b, a_not_match_b)
b_not_match_c = fill_match_list(b, c, b_not_match_c)
a_not_match_c = fill_match_list(a, c, a_not_match_c)

ans = 3*M
for b_idx in range(-2*M, 2*M):
    for c_idx in range(-2*M, 2*M):
        if not a_not_match_b[b_idx + cons] and not a_not_match_c[c_idx + cons] and not b_not_match_c[c_idx - b_idx + cons]:
            ans = min(ans, max(A, B + b_idx, C + c_idx) - min(0, b_idx, c_idx))

print(ans)

Solution (Python):
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, 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()

Solution (Python):


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

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

M = max(A, B, C)
cons = 6*M
a_not_match_b = [False] * 2 * cons
b_not_match_c = [False] * 2 * cons
a_not_match_c = [False] * 2 * cons

def fill_match_list(d1, d2, l):
    for i in range(len(d1)):
        for j in range(len(d2)):
            if d1[i] != d2[j] and d1[i] != "?" and d2[j] != "?":
                l[i-j+cons] = True
    return l

a_not_match_b = fill_match_list(a, b, a_not_match_b)
b_not_match_c = fill_match_list(b, c, b_not_match_c)
a_not_match_c = fill_match_list(a, c, a_not_match_c)

ans = 3*M
for b_idx in range(-2*M, 2*M):
    for c_idx in range(-2*M, 2*M):
        if not a_not_match_b[b_idx + cons] and not a_not_match_c[c_idx + cons] and not b_not_match_c[c_idx - b_idx + cons]:
            ans = min(ans, max(A, B + b_idx, C + c_idx) - min(0, b_idx, c_idx))

print(ans)