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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)


def js(s1, s2):

    for i in range(len(s1)):
        flag = True
        for j in range(0, min(len(s1) - i, len(s2))):
            c1 = s1[i + j]
            c2 = s2[j]

            if c1 != '?' and c2 != '?' and c1 != c2:
                flag = False
                break

        if flag:
            if len(s1) >= len(s2) + i:
                l1 = list(s1)
                for j in range(len(s2)):
                    if s1[i + j] == '?':
                        l1[i+j] = s2[j]
                return "".join(l1)
            else:
                l2 = list(s2)
                for j in range(i, len(s1)):
                    if s2[j - i] == '?':
                        l2[j - i] = s1[j]
                return s1[:i] + "".join(l2)
    return s1 + s2


def main():
    a = input()
    b = input()
    c = input()

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

    abc = js(ab, c)
    acb = js(ac, b)
    bac = js(ba, c)
    bca = js(bc, a)
    cab = js(ca, b)
    cba = js(cb, a)

    print(min(len(s) for s in (abc, acb, bac, bca, cab, cba)))


main()

Submission status: Wrong Answer

Solution code:
from itertools import permutations
def match(a,b):
    nb = len(b)
    na = len(a)
    n=min(nb,na)
    res=0
    for i in range(1,n+1):
        for j in range(i):
            if not(a[na-i+j] == b[j] or a[na-i+j] == '?' or  b[j] == '?'):
                break
        else:
            res=max(res,i)
    return res


a = input()
b = input()
c = input()
stls = [a,b,c]
ans=1001001001

for ls in permutations(stls):
    ansstring = ls[0]
    idx = match(ansstring, ls[1])
    ansstring += ls[1][idx:]
    idx = match(ansstring, ls[2])
    ansstring += ls[2][idx:]
    ans=min(ans,len(ansstring))

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
c = sys.stdin.readline().strip()
def match(x, y):
    
    for i in range(len(x)):
        if x[i] != "?":
            if y[i] != "?":
                if x[i] != y[i]:
                    return False
    return True

def do(a,b,c):
    #print (a,b,c)
    res = ""
    # a b c
    max_step = min(len(a), len(b))
    for p in range(max_step):
        if match(a[len(a) - max_step + p:], b[:max_step-p]):
            # merge the string
            res = a[:p]
            for j in range(max_step - p):
                if a[j+p] != "?":
                    res += a[j+p]
                else:
                    res += b[j]
            
            res += b[max_step-p:]
            break
    if res == "":
        res = a+b
    #print(res)
    a = res
    b = c
    #print(before)
    
    #print(a,b)
    max_step = min(len(a), len(b))
    for p in range(max_step):
        #print(p)
        if match(a[len(a) - max_step + p:], b[:max_step-p]):
            # merge the string
            return  len(b) + len(a) - (max_step-p)
    
    return len(a) + len(b)

tests = []
tests.append(do(a,b,c))
tests.append(do(a,c,b))
tests.append(do(b,a, c))
tests.append(do(b,c, a))
tests.append(do(c, b, a))
tests.append(do(c, a, b))
print(min(tests))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = [input() for i in range(3)]
    ans = float("inf")
    for p in permutations(range(3)):
        a,b,c = s[p[0]],s[p[1]],s[p[2]]
        ab = set([(a+b,True)])
        for i in range(len(a)):
            for j in range(min(len(a)-i,len(b))):
                k = i+j
                if k < len(a) and a[k] != b[j] and a[k] != "?" and b[j] != "?":
                    break
            else:
                if len(a)-i <= len(b):
                    d = a[:i]
                    for j in range(len(a)-i):
                        k = i+j
                        if a[k] == "?":
                            d += b[j]
                        else:
                            d += a[k]
                    for j in range(len(a)-i,len(b)):
                        d += b[j]
                    ab.add((d,d[-len(b)]==b))
                else:
                    d = a[:i]
                    for j in range(len(b)):
                        k = i+j
                        if b[j] == "?":
                            d += a[k]
                        else:
                            d += b[j]
                    for j in range(len(b),len(a)-i):
                        d += a[i+j]
                    ab.add((d,d[-len(b)]==b))
        bc = len(c)
        for i in range(len(b)):
            for j in range(min(len(b)-i,len(c))):
                k = i+j
                if k < len(b) and b[k] != c[j] and b[k] != "?" and c[j] != "?":
                    break
            else:
                if len(b)-i <= len(c):
                    bc = len(c)-(len(b)-i)
                else:
                    bc = 0
                break
        ac = len(c)
        for i in range(len(a)):
            for j in range(min(len(a)-i,len(c))):
                k = i+j
                if k < len(a) and a[k] != c[j] and a[k] != "?" and c[j] != "?":
                    break
            else:
                if len(a)-i <= len(c):
                    ac = len(c)-(len(a)-i)
                else:
                    ac = 0
                break
        res = len(a)+len(b)+len(c)
        for d,f in ab:
            if f:
                k = len(d)+bc
            else:
                k = len(d)+ac
            if k < res:
                res = k
        if res < ans:
            ans = res
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)


def js(s1, s2):

    for i in range(0, len(s1)):
        flag = True
        for j in range(0, min(len(s1) - i, len(s2))):
            c1 = s1[i + j]
            c2 = s2[j]

            if c1 != '?' and c2 != '?' and c1 != c2:
                flag = False
                break

        if flag:
            if len(s1) > len(s2) + i:
                l1 = list(s1)
                for j in range(len(s2)):
                    if s1[i + j] == '?':
                        l1[i+j] = s2[j]
                return "".join(l1)
            else:
                l2 = list(s2)
                for j in range(i, len(s1)):
                    if s2[j - i] == '?':
                        l2[j - i] = s1[j]
                return s1[:i] + "".join(l2)
    return s1 + s2


def main():
    a = input()
    b = input()
    c = input()

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

    abc = js(ab, c)
    acb = js(ac, b)
    bac = js(ba, c)
    bca = js(bc, a)
    cab = js(ca, b)
    cba = js(cb, a)

    # for s in (abc, acb, bac, bca, cab, cba):
    #    print(s)

    print(min(len(s) for s in (abc, acb, bac, bca, cab, cba)))


main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)


def js(s1, s2):

    for i in range(0, len(s1)):
        flag = True
        for j in range(0, min(len(s1) - i, len(s2))):
            c1 = s1[i + j]
            c2 = s2[j]

            if c1 != '?' and c2 != '?' and c1 != c2:
                flag = False
                break

        if flag:
            if len(s1) > len(s2) + i:
                l1 = list(s1)
                for j in range(len(s2)):
                    if s1[i + j] == '?':
                        l1[i+j] = s2[j]
                return "".join(l1)
            else:
                l2 = list(s2)
                for j in range(i, len(s1)):
                    if s2[j - i] == '?':
                        l2[j - i] = s1[j]
                return s1[:i] + "".join(l2)
    return s1 + s2


def main():
    a = input()
    b = input()
    c = input()

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

    abc = js(ab, c)
    acb = js(ac, b)
    bac = js(ba, c)
    bca = js(bc, a)
    cab = js(ca, b)
    cba = js(cb, a)

    for s in (abc, acb, bac, bca, cab, cba):
        print(s)

    print(min(len(s) for s in (abc, acb, bac, bca, cab, cba)))


main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    s = [input() for i in range(3)]
    ans = float("inf")
    for p in permutations(range(3)):
        a,b,c = s[p[0]],s[p[1]],s[p[2]]
        ab = set([a+b])
        for i in range(len(a)):
            for j in range(min(len(a)-i,len(b))):
                k = i+j
                if k < len(a) and a[k] != b[j] and a[k] != "?" and b[j] != "?":
                    break
            else:
                if len(a)-i <= len(b):
                    d = a[:i]
                    for j in range(len(a)-i):
                        k = i+j
                        if a[k] == "?":
                            d += b[j]
                        else:
                            d += a[k]
                    for j in range(len(a)-i,len(b)):
                        d += b[j]
                    ab.add(d)
                else:
                    d = a[:i]
                    for j in range(len(b)):
                        k = i+j
                        if b[j] == "?":
                            d += a[k]
                        else:
                            d += b[j]
                    for j in range(len(b),len(a)-i):
                        d += a[i+j]
                    ab.add(d)
        bc = len(c)
        for i in range(len(b)):
            for j in range(min(len(b)-i,len(c))):
                k = i+j
                if k < len(b) and b[k] != c[j] and b[k] != "?" and c[j] != "?":
                    break
            else:
                if len(b)-i <= len(c):
                    bc = len(c)-(len(b)-i)
                else:
                    bc = 0
                break
        ac = len(c)
        for i in range(len(a)):
            for j in range(min(len(a)-i,len(c))):
                k = i+j
                if k < len(a) and a[k] != c[j] and a[k] != "?" and c[j] != "?":
                    break
            else:
                if len(a)-i <= len(c):
                    ac = len(c)-(len(a)-i)
                else:
                    ac = 0
                break
        res = len(a)+len(b)+len(c)
        for d in ab:
            if d[-len(b):] == b:
                k = len(d)+bc
            else:
                k = len(d)+ac
            if k < res:
                res = k
        if res < ans:
            ans = res
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def check(s1, s2, pos):
    if pos >= 0:
        for i in range(min(len(s1)-pos, len(s2))):
            c1 = s1[i+pos]
            c2 = s2[i]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True
    else:
        pos = -pos
        for i in range(min(len(s1), len(s2)-pos)):
            c1 = s1[i]
            c2 = s2[i+pos]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True

checks = [set() for _ in range(3)]
def main():
    a = input()
    b = input()
    c = input()
    ls = [a, b, c]
    m = sum(len(s) for s in ls)
    ans = m
    for j in range(3):
        s1 = ls[j]
        s2 = ls[(j+1)%3]
        for i in range(-len(s2)+1, len(s1)):
            if check(s1, s2, i):
                checks[j].add(i)
                l = min(0, i)
                r = max(len(s1), len(s2)+i)
                ans = min(ans, r-l+len(ls[(j+2)%3]))
        # print(j, s1, s2, checks[j])
    for j in range(3):
        for c1 in checks[j]:
            for c2 in checks[(j+1)%3]:
                c3 = c1+c2
                # print(c1, c2, c3)
                l3 = len(ls[(j+2)%3])
                l = min(0, c1, c3)
                r = max(len(ls[j]), len(ls[(j+1)%3])+c1, len(ls[(j+2)%3])+c3)
                if r-l >= ans:
                    continue
                if c3 <= -l3 or c3 >= l3:
                    ans = min(ans, r-l)
                    continue
                if c3 in checks[(j+2)%3]:
                    # print(c1, c2, c3)
                    ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def check(s1, s2, pos):
    if pos >= 0:
        for i in range(min(len(s1)-pos, len(s2))):
            c1 = s1[i+pos]
            c2 = s2[i]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True
    else:
        pos = -pos
        for i in range(min(len(s1), len(s2)-pos)):
            c1 = s1[i]
            c2 = s2[i+pos]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True

checks = [set() for _ in range(3)]
def main():
    a = input()
    b = input()
    c = input()
    ls = [a, b, c]
    m = sum(len(s) for s in ls)
    ans = m
    for j in range(3):
        s1 = ls[j]
        s2 = ls[(j+1)%3]
        for i in range(-len(s2)+1, len(s1)):
            if check(s1, s2, i):
                checks[j].add(i)
                l = min(0, i)
                r = max(len(s1), len(s2)+i)
                ans = min(ans, r-l+len(ls[(j+2)%3]))
        # print(j, s1, s2, checks[j])
    for j in range(3):
        for c1 in checks[j]:
            for c2 in checks[(j+1)%3]:
                c3 = c1+c2
                # print(c1, c2, c3)
                l3 = len(ls[(j+2)%3])
                l = min(0, c1, c3)
                r = max(len(ls[j]), len(ls[(j+1)%3])+c1, len(ls[(j+2)%3])+c3)
                if c3 <= -l3 or c3 >= l3:
                    ans = min(ans, r-l)
                    continue
                if c3 in checks[(j+2)%3]:
                    # print(c1, c2, c3)
                    ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
s = []; ans = 0
for _ in range(3):
    s.append(input())
for x in s:
    ans += len(x)
a = [[0,1,2],[0,2,1],[1,0,2],[1,2,0],[2,1,0],[2,0,1]]
def check(s,t):
    for i in range(len(s)):
        k = i; j = 0;
        while k < len(s) and j < len(t):
            if s[k]=='?' or t[j]=='?' or s[k]==t[j]:
                k += 1; j += 1;
            else:
                break
        if k == len(s):
            return s[:i] + t
        if j == len(t):
            return s
    return s + t
def solve(s,t,e):
    global ans
    for i in range(len(s)):
        k = i; j = 0;
        while k < len(s) and j < len(t):
            if s[k]=='?' or t[j]=='?' or s[k]==t[j]:
                k += 1; j += 1;
            else:
                break
        if k == len(s):
            ans = min(ans,len(check(s[:i]+t,e)))
        if j == len(t):
            ans = min(ans,len(check(s,e)))
for b in a:
    solve(s[b[0]],s[b[1]],s[b[2]])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
A=input()
B=input()
C=input()
def chk(X,Y,i):
  k=min(len(X)-i,len(Y))
  for j in range(k):
    if X[i+j]=="?" or Y[j]=="?" or X[i+j]==Y[j]:
      continue
    else:
      return False
  else:
    return True
a,b,c=len(A),len(B),len(C)
ans=a+b+c
def f(X,Y,Z):
  x,y,z=len(X),len(Y),len(Z)
  xy=0
  for i in range(x):
    if chk(X,Y,i):
      xy=i+1
      break

  if xy==0:
    XY=X+Y
  else:
    XY=X[:xy-1]
    for i in range(y):
      if xy-1+i<x and X[xy-1+i]=="?" and Y[i]=="?":
        XY+="?"
      elif xy-1+i<x and X[xy-1+i]!="?":
        XY+=X[xy-1+i]
      else:
        XY+=Y[i]
  if xy!=0 and x>xy-1+y:
    XY+=X[xy-1+y:]
  if xy==0:
    xy=x+y
  else:
    xy=max(xy-1+y,x)
  xyz=0
  for i in range(xy):
    if chk(XY,Z,i):
      xyz=i+1
  if xyz==0:
    ret=xy+z
  else:
    ret=max(xy,xyz-1+z)
  xyz=0
  for i in range(z):
    if chk(Z,XY,i):
      xyz=i+1
  if xyz==0:
    ret=min(ret,xy+z)
  else:
    ret=min(ret,max(z,xyz-1+xy))
  return ret

ans=min(ans,f(A,B,C))
ans=min(ans,f(A,C,B))
ans=min(ans,f(B,A,C))
ans=min(ans,f(B,C,A))
ans=min(ans,f(C,A,B))
ans=min(ans,f(C,B,A))
print(ans)

Submission status: Wrong Answer

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


def stack2(a, b):
    max_reduce = min(len(a), len(b))
    reduce = 0
    stacked = a + b
    for i in reversed(range(max_reduce)):
        a_end = a[len(a)-i-1:]
        b_begin = b[:i+1]
        flag = True
        for j in range(len(a_end)):
            if a_end[j] != b_begin[j] and a_end[j] != '?' and b_begin[j] != '?':
                flag = False
                break
        if flag == True:
            reduce = len(a_end)
            a_begin = a[:len(a) - i - 1]
            b_end = b[i+1:]
            mid = ''
            for k in range(i+1):
                if a_end[k] != '?':
                    letter = a_end[k]
                else:
                    letter = b_begin[k]
                mid = mid + letter
            stacked = a_begin + mid + b_end
            break
    return stacked, reduce

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

r1 = stack2(a, b)[1] + stack2(stack2(a, b)[0], c)[1]
r2 = stack2(a, c)[1] + stack2(stack2(a, c)[0], b)[1]
r3 = stack2(b, a)[1] + stack2(stack2(b, a)[0], c)[1]
r4 = stack2(b, c)[1] + stack2(stack2(b, c)[0], a)[1]
r5 = stack2(c, a)[1] + stack2(stack2(c, a)[0], b)[1]
r6 = stack2(c, b)[1] + stack2(stack2(c, b)[0], a)[1]

r = max(r1, r2, r3, r4, r5, r6)

print(S-r)

Submission status: Wrong Answer

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

def eq_wc(s1,s2):
  len_s=len(s1)
  for i in range(len_s):
    if s1[i]!=s2[i] and s1[i]!="?" and s2[i]!="?":
      return False
  return True

def merge_abc(aa,bb,cc):
  #print(aa,bb,cc)
  match=0
  for i in range(1,min(len(aa),len(bb))+1):
    sub1=aa[-i:]
    sub2=bb[:i]
    #print(sub1,sub2)
    if eq_wc(sub1,sub2):
      match=i

  ab=[]
  for i in range(len(aa)-match):
    ab.append(aa[i])
  for i in range(match):
    if aa[len(aa)-match+i]==bb[i]:
      ab.append(bb[i])
    elif aa[len(aa)-match+i]=="?":
      ab.append(bb[i])
    else:
      ab.append(aa[len(aa)-match+i])
  for i in range(len(bb)-match):
    ab.append(bb[i+match])  
  
  match=0
  for i in range(1,min(len(ab),len(cc))+1):
    sub1=ab[-i:]
    sub2=cc[:i]
    #print(sub1,sub2)
    if eq_wc(sub1,sub2):
      match=i
  abc=[]
  for i in range(len(ab)-match):
    abc.append(ab[i])
  for i in range(match):
    if ab[len(ab)-match+i]==cc[i]:
      abc.append(cc[i])
    elif ab[len(ab)-match+i]=="?":
      abc.append(cc[i])
    else:
      abc.append(ab[len(ab)-match+i])
  for i in range(len(cc)-match):
    abc.append(cc[i+match])
  
  #print(len(abc),abc)
  return abc

abc=merge_abc(a,b,c)
acb=merge_abc(a,c,b)
bac=merge_abc(b,a,c)
bca=merge_abc(b,c,a)
cab=merge_abc(c,a,b)
cba=merge_abc(c,b,a)

#print(acb)
print(min(len(abc),len(acb),len(bac),len(bca),len(cab),len(cba)))

Submission status: Wrong Answer

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
A=input()
B=input()
C=input()
def chk(X,Y,i):
  k=min(len(X)-i,len(Y))
  for j in range(k):
    if X[i+j]=="?" or Y[j]=="?" or X[i+j]==Y[j]:
      continue
    else:
      return False
  else:
    return True
a,b,c=len(A),len(B),len(C)
ans=a+b+c
def f(X,Y,Z):
  x,y,z=len(X),len(Y),len(Z)
  xy=0
  for i in range(x):
    if chk(X,Y,i):
      xy=i+1
      break

  if xy==0:
    XY=X+Y
  else:
    XY=X[:xy-1]
    for i in range(y):
      if xy-1+i<x and X[xy-1+i]=="?" and Y[i]=="?":
        XY+="?"
      elif xy-1+i<x and X[xy-1+i]!="?":
        XY+=X[xy-1+i]
      else:
        XY+=Y[i]
  if xy!=0 and x>xy-1+y:
    XY+=X[xy-1+y:]
  if xy==0:
    xy=x+y
  else:
    xy=max(xy-1+y,x)
  xyz=0
  for i in range(xy):
    if chk(XY,Z,i):
      xyz=i+1
  if xyz==0:
    return xy+z
  else:
    return max(xy,xyz-1+z)

ans=min(ans,f(A,B,C))
ans=min(ans,f(A,C,B))
ans=min(ans,f(B,A,C))
ans=min(ans,f(B,C,A))
ans=min(ans,f(C,A,B))
ans=min(ans,f(C,B,A))
print(ans)

Submission status: Wrong Answer

Solution code:
a = [input(),input(),input()]
def checkEqual(l,r,k):
    i = len(l)-k
    j = 0
    for a in range(k):
        x, y = i+a, j+a
        if l[x] != r[y]:
            if l[x]=='?' or r[y]=='?':
                continue
            return False
    return True

overLaps = [[[] for i in range(3)] for j in range(3)]
ij = [(0,1),(1,0),(1,2),(2,1),(0,2),(2,0)]
for i,j in ij:
    l = a[i]
    r = a[j]
    m = min(len(l),len(r))
    for k in range(m+1):
        if checkEqual(l,r,k):
            overLaps[i][j].append(k)

maxRe = 0
combs = [(0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0)]
for x,y,z in combs:
    full = len(a[y])
    o1 = overLaps[x][y]
    o2 = overLaps[y][z]
    midOl = set(overLaps[x][z])
    for i in range(len(o1)-1,-1,-1):
        for j in range(len(o2)-1,-1,-1):
            re = o1[i] + o2[j]
            if re > full:
                if re-full not in midOl:
                    continue
            maxRe = max(re,maxRe)
    # i = len(o1)-1
    # j = len(o2)-1
    # if o1[i] + o2[j] <= full:
    #     re = o1[i] + o2[j]
    #     maxRe = max(re,maxRe)
    #     continue
    #
    # bar = full - o1[i]
    # while o2[j] > bar:
    #     j -= 1
    #     if j == 0:
    #         break
    # while j < len(o2):
    #     bar = full - o2[j]
    #     while o1[i] > bar:
    #         i -= 1
    #         if i<0:
    #             break
    #     if i<0:
    #         break
    #     re = o1[i] + o2[j]
    #     maxRe = max(re,maxRe)
    #     j += 1

ans = len(a[0])+len(a[1])+len(a[2])-maxRe
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
import itertools

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

def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = (word[i] == word[j] or word[i]=='?' or word[j]=='?')

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table
 
def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0

    while i < len(text) and p < len(word):
        if (text[i] == word[p] or text[i]=='?' or word[p]=='?'):
            i += 1
            p += 1
        elif p == 0:
            i += 1
        else:
            p = table[p]
    
    if p==len(word):
        return [True, p]
    else:
        return [False, p]
        
 

L = len(S[0])+len(S[1])+len(S[2])
ans = 10**9+10
for order in itertools.permutations([0,1,2]):
    res = L
    minus = 0
    flag,p = kmp_search(S[order[0]],S[order[1]])
    minus += p
    if flag:
        flag,p = kmp_search(S[order[0]],S[order[2]])
    else:
        flag,p = kmp_search(S[order[1]],S[order[2]])
    minus += p
    
    ans = min(ans,res-minus)
print(ans)

Submission status: Wrong Answer

Solution code:
a = input()
b = input()
c = input()
p = len(a)
q = len(b)
r = len(c)


def func(a, b):
    p = len(a)
    q = len(b)
    for i in range(p):
        f = 0
        z = min(q, p - i)
        for j in range(z):
            if a[j + i] != "?" and b[j] != "?" and a[j + i] != b[j]:
                break
            f += 1
        if f == z:
            res = []
            for j in range(i):
                res.append(a[j])
            if p > q + i:
                for j in range(q):
                    if a[i + j] == "?":
                        res.append(b[j])
                    else:
                        res.append(a[i + j])
                for j in range(p - q - i, p):
                    res.append(a[j])
            elif p == q + i:
                for j in range(q):
                    if a[i + j] == "?":
                        res.append(b[j])
                    else:
                        res.append(a[i + j])
            else:
                for j in range(p - i):
                    if a[i + j] == "?":
                        res.append(b[j])
                    else:
                        res.append(a[i + j])
                for j in range(p - i, q):
                    res.append(b[j])
            return "".join(map(str, res))
    return a + b


res = []
res.append(func(func(a, b), c))
res.append(func(func(a, c), b))
res.append(func(func(b, a), c))
res.append(func(func(b, c), a))
res.append(func(func(c, a), b))
res.append(func(func(c, b), a))

result = 10 * 8
for sres in res:
    result = min(result, len(sres))
print(result)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def check(s1, s2, pos):
    if pos >= 0:
        for i in range(min(len(s1)-pos, len(s2))):
            c1 = s1[i+pos]
            c2 = s2[i]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True
    else:
        pos = -pos
        for i in range(min(len(s1), len(s2)-pos)):
            c1 = s1[i]
            c2 = s2[i+pos]
            if c1 == c2:
                continue
            if c1 == '?' or c2 == '?':
                continue
            return False
        return True

checks = [set() for _ in range(3)]
def main():
    a = input()
    b = input()
    c = input()
    ls = [a, b, c]
    m = sum(len(s) for s in ls)
    ans = m
    for j in range(3):
        s1 = ls[j]
        s2 = ls[(j+1)%3]
        for i in range(-len(s2)+1, len(s1)):
            if check(s1, s2, i):
                checks[j].add(i)
                l = min(0, i)
                r = max(len(s1), len(s2)+i)
                ans = min(ans, r-l+len(ls[(j+2)%3]))
        # print(j, s1, s2, checks[j])
    for c1 in checks[0]:
        for c2 in checks[1]:
            c3 = c1+c2
            if c3 in checks[2]:
                l = min(0, c1, c3)
                r = max(len(ls[0]), len(ls[1])+c1, len(ls[2])+c3)
                ans = min(ans, r-l)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def make_index(A, B):
    I = []
    for i in range(len(A)):
        for j in range(min(len(B), len(A) - i)):
            if A[i + j] == "?":
                continue

            if B[j] == "?":
                continue

            if A[i + j] != B[j]:
                break
        else:
            I.append(i)
        
    I.append(len(A))
    return I


def check(AB, BC, AC, len_c):
    import bisect

    res = 10 ** 20
    for i in AB:
        for j in BC:
            if i + j < AB[-1]:
                t = bisect.bisect_left(AC, i + j) 
                if AC[t] != i + j:
                    continue
            res = min(res, max(AB[-1], i + BC[-1], i + j + len_c))
    return res


def main():
    A = input().strip()
    B = input().strip()
    C = input().strip()
    AB = make_index(A, B)
    BA = make_index(B, A)
    BC = make_index(B, C)
    CB = make_index(C, B)
    CA = make_index(C, A)
    AC = make_index(A, C)

    res = min(
        check(AB, BC, AC, len(C)), 
        check(BA, AC, BC, len(C)), 
        check(BC, CA, BA, len(A)), 
        check(CB, BA, CA, len(A)), 
        check(CA, AB, CB, len(B)), 
        check(AC, CB, AB, len(B))
        )
    print(max(res, 1))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:

from itertools import permutations

def match(s, t):
    results = [s + t]
    for i in range(len(s)):
        # i文字分をずらす
        res = s[:i]
        check = True
        for sc, tc in zip(s[i:], t):
            if sc == tc:
                res += sc
            elif sc == '?':
                res += tc
            elif tc == '?':
                res += sc
            else:
                check = False
                break

        res += t[len(s) - i:]

        if check:
            results.append(res)

    return results
                

def submit():
    a = input()
    b = input()
    c = input()

    min_len = float('inf')
    for s1, s2, s3 in permutations([a, b, c]):
        cand = match(s1, s2)
        cand = list(set(cand))
        for c in cand:
            t = match(c, s3)
            for e in t:
                if min_len > len(e):
                    min_len = len(e)

    print(min_len)

if __name__ == "__main__":
    submit()