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:
import sys, itertools
range = xrange
input = raw_input

orda = ord('a')

A = [ord(c) - orda for c in input()]
B = [ord(c) - orda for c in input()]
C = [ord(c) - orda for c in input()]

A = [-1 if a == - 34 else a for a in A]
B = [-1 if a == - 34 else a for a in B]
C = [-1 if a == - 34 else a for a in C]

An = len(A)
Bn = len(B)
Cn = len(C)

 
ABhit = []
AChit = []
BChit = []

big = 4010
for i in range(-big,big):
#for i in range(-Bn, An + 1):
    for j in range(max(0, i), min(An, Bn + i)):
        if A[j] != -1 and B[j - i] != -1 and A[j] != B[j - i]:
            break
    else:
        ABhit.append(i)

for i in range(-big,big):
#for i in range(-Cn, An + 1):
    for j in range(max(0, i), min(An, Cn + i)):
        if A[j] != -1 and C[j - i] != -1 and A[j] != C[j - i]:
            break
    else:
        AChit.append(i)

for i in range(-big,big):
#for i in range(-Cn, Bn + 1):
    for j in range(max(0, i), min(Bn, Cn + i)):
        if B[j] != -1 and C[j - i] != -1 and B[j] != C[j - i]:
            break
    else:
        BChit.append(i)

best = An + Bn + Cn
for i in ABhit:
    ind1 = 0
    ind2 = 0
    # AChit[ind1] - BChit[ind2] = i
    while ind1 < len(AChit) and ind2 < len(BChit):
        if AChit[ind1] - BChit[ind2] < i:
            ind1 += 1
        elif AChit[ind1] - BChit[ind2] > i:
            ind2 += 1
        else:
            j = AChit[ind1]
            best = min(best, max(An, Bn + i, Cn + j) - min(0,i,j))
            ind1 += 1

#print ABhit
#print AChit
#print BChit
print best

Submission status: Accepted

Solution code:
K = 4000
A = input()
B = input()
C = input()
la, lb, lc = len(A), len(B), len(C)

def check(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

AB = check(A, B)
AC = check(A, C)
BC = check(B, C)

mi = K * 3
for ib in range(-K, K + 1):
    if AB[ib] == 0: continue
    for ic in range(-K, K + 1):
        if AC[ic] == 0 or BC[ic - ib] == 0: continue
        mi = min(mi, max(ib + lb, ic + lc, la) - min(ib, ic, 0))

print(mi)

Submission status: Accepted

Solution code:
K = 4000
A = input()
B = input()
C = input()
la, lb, lc = len(A), len(B), len(C)

def check(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

AB = check(A, B)
AC = check(A, C)
BC = check(B, C)

mi = K * 3
for i_ab in range(-K, K + 1):
    if AB[i_ab] == 0: continue
    for i_ac in range(max(-K, min(i_ab, 0) - lc), min(K + 1, max(la, i_ab + lb))):
        if AC[i_ac] == 0: continue
        if BC[i_ac - i_ab] == 0: continue
        mi = min(mi, max(i_ab + lb, i_ac + lc, la) - min(i_ab, i_ac, 0))

print(mi)

Submission status: Runtime Error

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
aを固定して，b，cの位置を全探索
"""
def main():
    mod=10**9+7
    a=input()
    b=input()
    c=input()
    M=2005
    
    Na=len(a)
    Nb=len(b)
    Nc=len(c)
    
    def ch(c1,c2):
        return c1==c2 or c1=="?" or c2=="?"
    
    # aを左端に固定，bがbi文字目から,cが(bからみて)ci文字目から始まるとして，どうなるか
    # 実際にはabcの並びが6通り
    def calc(s1,s2,s3):
        
        # 遠く離れている場合などもokなので，初期値は1，ダメなら0に
        ab=[1]*(2*M)
        ac=[1]*(2*M)
        bc=[1]*(2*M)
        
        for bi in range(Na):#aの何文字目から?
            for j in range(Nb):#bの何文字目？
                if bi+j>=Na:
                    break
                if not ch(s1[bi+j], s2[j]):
                    ab[bi]=0
                    break
                
        for ci in range(Na):#aの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Na:
                    break
                if not ch(s1[ci+j], s3[j]):
                    ac[ci]=0
                    break
                
        for ci in range(Na):#bの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Nb:
                    break
                if not ch(s2[ci+j], s3[j]):
                    bc[ci]=0
                    break
                
        ans=10**5
        for i in range(Na+1):#bの開始位置
            for j in range(i,2*M):#cの開始位置
                if ab[i] and ac[j] and bc[j-i]:
                    ans=min(ans,j+Nc)
                    
        # print(ab)
        # print(ac)
        # print(bc)
                    
        return ans
    
    ans=10**5
    
    ans=min(ans,calc(a,b,c))
    ans=min(ans,calc(a,c,b))
    ans=min(ans,calc(b,a,c))
    ans=min(ans,calc(b,c,a))
    ans=min(ans,calc(c,a,b))
    ans=min(ans,calc(c,b,a))
    
    print(ans)
                
            
        
            
    

    
    
                

    
        
    

main()

Submission status: Runtime Error

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
aを固定して，b，cの位置を全探索
"""
def main():
    mod=10**9+7
    a=input()
    b=input()
    c=input()
    M=2005
    
    Na=len(a)
    Nb=len(b)
    Nc=len(c)
    
    def ch(c1,c2):
        return c1==c2 or c1=="?" or c2=="?"
    
    # aを左端に固定，bがbi文字目から,cが(bからみて)ci文字目から始まるとして，どうなるか
    # 実際にはabcの並びが6通り
    def calc(s1,s2,s3):
        
        # 遠く離れている場合などもokなので，初期値は1，ダメなら0に
        ab=[1]*(2*M)
        ac=[1]*(2*M)
        bc=[1]*(2*M)
        
        for bi in range(Na):#aの何文字目から?
            for j in range(Nb):#bの何文字目？
                if bi+j>=Na:
                    break
                if not ch(s1[bi+j], s2[j]):
                    ab[bi]=0
                    break
                
        for ci in range(Na):#aの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Na:
                    break
                if not ch(s1[ci+j], s3[j]):
                    ac[ci]=0
                    break
                
        for ci in range(Na):#bの何文字目から?
            for j in range(Nc):#cの何文字目？
                if ci+j>=Nb:
                    break
                if not ch(s2[ci+j], s3[j]):
                    bc[ci]=0
                    break
                
        ans=10**5
        for i in range(Na+1):#bの開始位置
            for j in range(i,i+Na+Nb):#cの開始位置
                if ab[i] and ac[j] and bc[j-i]:
                    ans=min(ans,j+Nc)
                    
        # print(ab)
        # print(ac)
        # print(bc)
                    
        return ans
    
    ans=10**5
    
    ans=min(ans,calc(a,b,c))
    ans=min(ans,calc(a,c,b))
    ans=min(ans,calc(b,a,c))
    ans=min(ans,calc(b,c,a))
    ans=min(ans,calc(c,a,b))
    ans=min(ans,calc(c,b,a))
    
    print(ans)
                
         
    

main()

Submission status: Runtime Error

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

len_a = len(a)
len_b = len(b)
len_c = len(c)

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


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

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+10000] = False

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

len_max = len(a)+len(b)+len(c)

ans = len_max
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+10000] and ac[j+10000] and bc[j-i+10000]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)

Submission status: Runtime Error

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

len_a = len(a)
len_b = len(b)
len_c = len(c)

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


ab = [True] * 9000
ac = [True] * 9000
bc = [True] * 9000

def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+4500] = False

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

len_max = len(a)+len(b)+len(c)

ans = len_max
for i in range(-2*len_max, 2*len_max+1):
    for j in range(-2*len_max, 2*len_max+1):
        if ab[i+4500] and ac[j+4500] and bc[j-i+4500]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
print(ans)

Submission status: Runtime Error

Solution code:
a=input()
b=input()
c=input()
A=len(a)
B=len(b)
C=len(c)
d={a:A, b:B, c:C}
d=sorted(d.items(),key=lambda x:x[1])
a=d[2][0]
b=d[1][0]
c=d[0][0]
A=d[2][1]
B=d[1][1]
C=d[0][1]
ans=[[a+b,A+B],[b+a,A+B]]
ans1=[[a+c,A+C],[c+a,C+A]]

def find(a,b,A,B,ans):
  for i in range(1,A+B):
    if i<=B:
      num=0
      for j in range(i):
        if a[j]==b[B-i+j] or (a[j]=="?") or (b[B-i+j]=="?"):
          num+=1
        else:
          break
        if num==i:
          ans.append([b[:B-i]+a,B-i+A])
    elif i<A:
      num=0
      for j in range(B):
        if a[i-B+1+j]==b[j] or (a[i-B+1+j]=="?") or (b[j]=="?"):
          num+=1
        else:
          break
        if num==i:
          ans.append([a,A])
    else:
      num=0
      for j in range(A+B-i):
        if (a[i-B+j]==b[j]) or (a[i-B+j]=="?") or (b[j]=="?"):
          num+=1
        else:
          break
        if num==A+B-i:
          ans.append([a+b[A-i:],i])
  return ans

ans=find(a,b,A,B,ans)
an=[]
for i in ans:
  an=find(i[0],c,i[1],C,an)
ans1=find(a,c,A,C,ans1)
for i in ans1:
  an=find(i[0],b,i[1],B,an)
mi=A+B+C
for i in an:
  if i[1]<mi:
    mi=i[1]
print(mi)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i,n) for(int i = 0; i<(int)(n); i++)
#define REPS(i,n) for (int i = 1; i<=(int)(n); i++)
#define REPD(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define MOD 1000000007
#define MOD2 998244353

vector<bool> ab(100000, true);
vector<bool> bc(100000, true);
vector<bool> ac(100000, true);

bool judge(char c1, char c2){
	return (c1 == '?' || c2 == '?' || c1 == c2);
}

int main(){
	string a, b, c;
	cin >> a >> b >> c;
	int A = a.length();
	int B = b.length();
	int C = c.length();

	int i, j;

	REP(i,A) REP(j,B) if (!judge(a[i], b[j])) ab.at(i-j+50000) = false;
	REP(i,A) REP(j,C) if (!judge(a[i], c[j])) ac.at(i-j+50000) = false;
	REP(i,B) REP(j,C) if (!judge(b[i], c[j])) bc.at(i-j+50000) = false;

	int ans = 6000;
	FOR(i,-4000,4000){
		FOR(j,-4000,4000){
			if (ab.at(i+50000) && ac.at(j+50000) && bc.at(j-i+50000)){
				int L = min(0, min(i,j));
				int R = max(A, max(B+i,C+j));
				ans = min(ans, R-L);
			}
		}
	}
	cout << ans << endl;
}

Submission status: Runtime Error

Solution code:
a = list(input())
b = list(input())
c = list(input())
s = len(a)

o = ((a,b), (a,c), (b,a), (b,c), (c,a), (c,b))

su = []

for i in range(6):
    d = o[i][0].copy()
    e = o[i][1].copy()

    tf = False
    for j in range(s):
        if tf == True:
            break

        for k in range(s-j):
            if d[j+k] != e[k] and e[k] != '?' and d[j+k] != '?':
                break

            if k == s - j - 1:
                tf = True
                su.append(j)

    if tf == False:
        su.append(s)

print(s + min([su[0]+su[3], su[1]+su[5], su[2]+su[1], su[3]+su[4], su[4]+su[0], su[5]+su[2]]))

Submission status: Runtime Error

Solution code:
a = list(input())
b = list(input())
c = list(input())
s = len(a)

o = ((a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a))

ans = []

for i in range(6):
    d = o[i][0].copy()
    e = o[i][1].copy()
    f = o[i][2].copy()

    ##
    tf = False
    for j in range(s):
        if tf == True:
            break

        res = []
        for k in range(s-j):
            if d[j+k] != e[k] and e[k] != '?' and d[j+k] != '?':
                break

            if d[j+k] == '?' and e[k] != '?':
                res.append(k)
            if k == s - j - 1:
                d += e[s - j:]
                for l in res:
                    d[j+l] = e[l]
                tf = True
                wc = s + j #word count

    if tf == False:
        d += e
        wc = s * 2

    ##
    tf = False
    for j in range(s):
        if tf == True:
            break

        for k in range(s - j):
            if d[-s+j+k] != f[k] and d[-s+j+k] != '?' and f[k] != '?':
                break

            if k == s - j - 1:
                d += e[s - j:]
                tf = True
                ans.append(wc + j)

    if tf == False:
        ans.append(wc + s)

print(min(ans))

Submission status: Runtime Error

Solution code:
# coding: utf-8
import re
A = input()
B = input()
C = input()

def _check(st1, st2):
    if len(st1) != len(st2):
        return False
    if st1 == st2:
        return True
    for i in range(len(st1)):
        if st1[i] == st2[i]:continue
        if (st1[i]=='?')|(st2[i]=='?'):continue
        else:
            return False
    return True

def check(A,B,C,x,y):
    if _check(A[x:x+len(B)], B[:len(A)-x]):
        if _check(B[y:y+len(C)], C[:len(B)-y]):
            if _check(A[x+y:], C[:len(A)-x-y]):
                return max([len(A), len(B)+x, len(C)+x+y])
    return len(A)+len(B)+len(C)


if __name__ == '__main__':
    min_val = 10**10
    patterns = [[A,B,C], [A,C,B], [B,A,C], [B,C,A], [C,A,B], [C,B,A]]
    for pattern in patterns:
        max_x = len(pattern[0])
        max_y = len(pattern[1])
        for x in range(max_x+1):
            for y in range(max_y+1):
                val = check(*pattern, x,y)
                if min_val > val:
                    min_val = val
    print(min_val)

Submission status: Runtime Error

Solution code:
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

#include "bits/stdc++.h"
using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i,a,b)  for(int i = a; i < b; i++)
#define endl '\n'
using ll = long long;
#define int ll
using db = long double;
using ii = pair<int, int>;

const int N = 1e5 + 5, LG = 19, MOD = 998244353;
const int SQ =320;
const long double EPS = 1e-7;

bool matched[3][3][2005];
string s[3];
void go(int x, int y){
  for(int j = 0; j < s[x].size(); j++){
    bool ok = true;
    for(int k = 0; k < s[y].size() && j + k < s[x].size() && ok; k++){
      ok &= (s[y][k] == s[x][j+k] || (s[y][k] == '?') || (s[x][j+k] == '?'));
    }
    matched[y][x][j] = ok;
  }
}
int32_t main(){
#ifdef ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
  memset(matched,1,sizeof matched);
  f(i,0,3)  cin >> s[i];
  f(i,0,3)f(j,0,3)go(i,j);
  int p[3] = {0,1,2};
  int ans = s[0].size() + s[1].size() + s[2].size();
  do{

    for(int i = 0; i <= s[p[0]].size(); i++){
      if(matched[p[1]][p[0]][i]){
        for(int j = 0; j <= s[p[1]].size() || i + j <= s[p[0]].size(); j++){
          if(matched[p[2]][p[1]][j] && matched[p[2]][p[0]][i + j]){
            ans = min(ans, max({(int)s[p[0]].size(),i+(int)s[p[1]].size(),i+j+(int)s[p[2]].size()}));
          }
        }
      }
    }

  }while(next_permutation(p,p+3));

  cout << ans << "\n";

  return 0;
}

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


a = S()
b = S()
c = S()
total_len = len(a) + len(b) + len(c)

def check(x, y):
    # xの後にy
    x_len = len(x)
    L = [0] * (x_len + 1)
    for y_start in range(x_len + 1):
        for j in range(x_len + 1):
            if y_start + j >= x_len:
                continue
            elif x[y_start + j] != y[j] and x[y_start + j] != '?' and y[j] != '?':
                break
        else:
            L[y_start] = 1
    return L


ans = total_len
for i, j, k in permutations((a, b, c)):
    ij_list = check(i, j)
    jk_list = check(j, k)
    ik_list = check(i, k)
    i_len = len(i)
    j_len = len(j)
    k_len = len(k)
    for ij_gap in range(len(i) + 1):
        for jk_gap in range(len(j) + 1):
            if ij_list[ij_gap] == 0 or jk_list[jk_gap] == 0:
                continue
            if ij_gap + jk_gap < i_len and ik_list[i_len - ij_gap - jk_gap] == 0:
                continue
            ans = min(ans, max(ij_gap + jk_gap + k_len, ij_gap + j_len, i_len))

print(ans)

Submission status: Runtime Error

Solution code:
import itertools

import numpy as np


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


def judge_array(x, y):
    l = [None] * 2001
    for i in range(2001):
        s = x[i:]
        t = y[:2001 - i]
        l[i] = np.all(np.where((s == t) | (s == 0) | (t == 0), True, False))
    return l


def main():
    n = [len(a), len(b), len(c)]
    d = {chr(ord('a') + i - 1): i for i in range(1, 27)}
    d['?'] = 0
    abc = np.full((3, 2001), np.zeros(2001))
    for i in range(2000):
        if i < n[0]:
            abc[0][i] = d[a[i]]
        if i < n[1]:
            abc[1][i] = d[b[i]]
        if i < n[2]:
            abc[2][i] = d[c[i]]

    w = [[None] * 3, [None] * 3, [None] * 3]
    for i in range(3):
        for j in range(3):
            if i == j:
                continue
            w[i][j] = judge_array(abc[i], abc[j])
    
    l = itertools.permutations([0, 1, 2])
    ans = 6000
    for x, y, z in l:
        xy = w[x][y]
        xz = w[x][z]
        yz = w[y][z]
        for i in range(2001):
            for j in range(2001):
                if xy[i] and yz[j] and xz[min(2000, i + j)]:
                    v = max(n[x], i + n[y], i + j + n[z])
                    ans = min(ans, v)
                    break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce
from itertools import permutations

S = [input() for _ in range(3)]

M = reduce(max, map(len, S))

match = [[[True]*(M*2+1) for _ in range(3)] for _ in range(3)]
cnt = 0
for x in range(3):
    for y in range(3):
        if x != y:
            for i in range(M*2+1):
                if len(S[x]) <= i:
                    break
                match[x][y][i] = False
                for j in range(len(S[x])-i):
                    cnt += 1
                    # print(x, y, i, j, S[x][i+j], S[y][j])
                    if S[x][i+j] != S[y][j] and S[x][i+j] != "?" and S[y][j] != "?":
                        break
                else:
                    match[x][y][i] = True

print(cnt)

print(match[0][1])


def check(i, j, p):
    A = p[0]
    B = p[1]
    C = p[2]
    if not match[A][B][i]:
        return False
    if not match[A][C][j]:
        return False
    if not match[B][C][j-i]:
        return False
    return True


ans = M*4

for p in permutations([0, 1, 2]):
    for i in range(len(S[p[0]])+1):
        for j in range(i, max(len(S[p[0]]), i+len(S[p[1]])+1)):
            len_full = max(len(S[p[0]]), i+len(S[p[1]]), j+len(S[p[2]]))
            if check(i, j, p) and len_full < ans:
                ans = len_full
print(ans)

Submission status: Runtime Error

Solution code:
from functools import reduce
from itertools import permutations

S = [input() for _ in range(3)]

M = reduce(max, map(len, S))

match = [[[False]*(M*3) for _ in range(3)] for _ in range(3)]

for x in range(3):
    for y in range(3):
        for i in range(M*3):
            if len(S[x]) <= i:
                match[x][y][i] = True
                continue
            for j in range(M*2):
                if i+j < len(S[x]):
                    # print(x, y, i, j, S[x][i+j], S[y][j])
                    if S[x][i+j] != S[y][j] and S[x][i+j] != "?" and S[y][j] != "?":
                        match[x][y][i] = True
            match[x][y][i] = not match[x][y][i]


def check(i, j, p):
    A = p[0]
    B = p[1]
    C = p[2]
    if not match[A][B][i]:
        return False
    if not match[A][C][j]:
        return False
    if not match[B][C][j-i]:
        return False
    return True


ans = M*4

for p in permutations([0, 1, 2]):
    for i in range(len(S[p[0]])+1):
        for j in range(i, max(len(S[p[0]]), i+len(S[p[1]])+1)):
            len_full = max(len(S[p[0]]), i+len(S[p[1]]), j+len(S[p[2]]))
            if check(i, j, p) and len_full < ans:
                ans = len_full
print(ans)

Submission status: Runtime Error

Solution code:
from itertools import permutations

ABC = [input().rstrip(), input().rstrip(), input().rstrip()]

cache = [-1] * (3 * 3)


def canMatchShifted(index1, index2, shift):
    # Whether ABC[index1] can match with ABC[index2] shifted to the right by `shift`
    k = 3 * index1 + index2
    if cache[k] == -1:
        S1 = ABC[index1]
        S2 = ABC[index2]
        temp = [True] * (4001)
        for s in range(len(S1)):
            temp[s] = all(x == y or x == "?" or y == "?" for x, y in zip(S1[s:], S2))
        cache[k] = temp

    return cache[k][shift]


# Try all permutation orders of ABC
best = float("inf")
for a, b, c in permutations(range(3)):
    A = ABC[a]
    B = ABC[b]
    C = ABC[c]
    # Match A with `('?' * i) + B`
    for i in range(len(A) + 2):
        if not canMatchShifted(a, b, i):
            continue
        # Match B with `('?' * j) + C`
        # Match A with `('?' * (i + j)) + C`
        for j in range(len(B) + 2):
            if canMatchShifted(b, c, j) and canMatchShifted(a, c, i + j):
                l = max(len(A), i + len(B), i + j + len(C))
                best = min(best, l)
print(best)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 12000, [1] * 12000, [1] * 120000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+6000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+6000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+6000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 12000, [1] * 12000, [1] * 120000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+6000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j 6000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+6000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[i] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+6000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[i] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+6000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[i] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+6000]= 0
ans = 6000

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Runtime Error

Solution code:
a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 120000, [1] * 120000, [1] * 120000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[i] == '?':
            continue
        if a[i] != b[j]:
            ab[i-j+6000]= 0
for i in range(B):
    if a[i] == '?':
        continue
    for j in range(C):
        if b[i] == '?':
            continue
        if b[i] != c[j]:
            bc[i-j+6000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if b[i] == '?':
            continue
        if a[i] != c[j]:
            ac[i-j+6000]= 0
ans = 6000

for i in range(-2000, 2000):
    for j in range(-2000, 2000):
        if ab[i+6000] and bc[j-i+6000] and ac[j+6000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)

Submission status: Runtime Error

Solution code:
def match(x, y):
    """
    １文字x, yが一致するか少なくとも一方が？であればTrueを返す。
    """
    return x == y or x == "?" or y == "?"


def func(a, b, c, la, lb, lc):
    """
    文字列の並びがa->b->cの場合を仮定して考える。
    aに対するb, cの配置が高々2000 * 2000通りあるので、文字列が一致するかの判定はO(1)でしないとTLE。
    これは先にaとb、bとc、aとcに対して文字列の一致を前処理確認しておけばOK <= 思いつかなかったので反省。

    ab[i] = (b[0]をa[i]から重ねたとき、合成文字列は一致するか)
    bc[i] = (c[0]をb[i]から重ねたとき、合成文字列は一致するか)
    ac[i] = (c[0]をa[i]から重ねたとき、合成文字列は一致するか)
    とおく。後ろに[True] * 2000を付け加えているのはaとbがdisjointな場合を考慮するため。
    """
    ab = [True] * (la + 2000)
    bc = [True] * (lb + 2000)
    ac = [True] * (la + 2000)

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

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

    for i in range(la):
        for j in range(min(la - i, lc)):
            if not match(a[i + j], c[j]):
                ac[i] = False
                break
    #print("ab={}".format(ab[:la]))
    #print("bc={}".format(bc[:lb]))
    #print("ac={}".format(ac[:la]))
    """
    前処理終わり。これより実際の比較を行う。
    """
    ans = la + lb + lc
    for i in range(la + 1):
        for j in range(max(lb + 1, la + 1 - i)): # A上でBとCがdisjointに乗っかっている場合、j <= lbだと不十分(ex. A = "qaawbbe", B = "aa", C = "bb")
            if ab[i] and bc[j] and ac[i + j]:
                preans = max(la, i + lb, i + j + lc) # ここ(i + lb)入れないと、Bが一番長い場合が抜け落ちる
                ans = min(ans, preans)
    #print("{}->{}->{}: ans={}".format(a, b, c, ans))
    return ans


def main():
    a = input()
    b = input()
    c = input()
    la = len(a)
    lb = len(b)
    lc = len(c)
    ans = func(a, b, c, la, lb, lc)
    ans = min(ans, func(a, c, b, la, lc, lb))
    ans = min(ans, func(b, a, c, lb, la, lc))
    ans = min(ans, func(b, c, a, lb, lc, la))
    ans = min(ans, func(c, a, b, lc, la, lb))
    ans = min(ans, func(c, b, a, lc, lb, la))
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

def love(x,y):
  #xy
  #i=zure
  for i in range(len(x)):
    flag=0
    for j in range(len(x)-i):
        if x[i+j]!=y[j]:
            if x[i+j]!="?" and y[j]!="?":
                flag=1
                break
    if flag==0:return len(x)-i
  return 0
    
#ab
ab=love(a,b)
#ac
ac=love(a,c)
#ba
ba=love(b,a)
#bc
bc=love(b,c)
#ca
ca=love(c,a)
#cb
cb=love(c,b)
result=len(a)+len(b)+len(c)
maxLength=result
#print(maxLength)
#print(ab,ac,ba,bc,ca,cb)
#abc
result=min(result,maxLength-ab-bc)
#acb
result=min(result,maxLength-ac-cb)
#bac
result=min(result,maxLength-ba-ac)
#bca
result=min(result,maxLength-bc-ca)
#cab
result=min(result,maxLength-ca-ab)
#cba
result=min(result,maxLength-cb-ba)
print(result)

Submission status: Runtime Error

Solution code:
from itertools import chain, permutations
from heapq import merge
from functools import wraps

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

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

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

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

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

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

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

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