AtCoder パナソニックプログラミングコンテスト2020 E問題　時間短縮の方法

前提・発生している問題・実現したいこと

AtCoder パナソニックプログラミングコンテスト2020 E問題にて以下のコードを提出しましたが、ほぼ全てのケースでTLEとなってしまいました。
計算速度向上のためにはどうすればよいでしょうか。
特に'???'を過剰に生成していることが原因かもしれない、と考えているのですが、具体的な解決方法が思いつきませんでした。
その他の解決方法でも構いません。
https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_e

該当のソースコード

Python
1A = input()
2B = input()
3C = input()
4
5def match(v,w): # 2つの文字を合わせられるかどうかを調べる
6    if(v != '?' and w != '?' and v != w):
7        return 0
8    else:
9        return 1
10
11def middle(x,y,z): # 3つの値の中間をとる。
12    X = [x,y,z] #どこから被りが発生するのかを探すことで、計算量が2/3程度になりそう
13    X.sort() 
14    return(X[1])
15
16
17def milen(a,b,c):
18    aa = len(a)
19    bb = len(b)
20    cc = len(c)
21
22    minlen = aa + bb + cc #　文字列の長さの最大値
23    s = '?'*(bb+cc) + a + '?'*(bb+cc)
24    for i in range(-bb-cc,aa+cc+1): # iが文字列Bの開始位置
25        t = '?'*(bb+cc+i) + b + '?'*(aa+cc-i)
26        for j in range(-bb-cc,aa+bb+1): # jが文字列Cの開始位置
27            u = '?'*(bb+cc+j) + c + '?'*(aa+bb-j)
28            flag = 1
29            for k in range(middle(0,i,j)+bb+cc,middle(aa,i+bb,j+cc)+bb+cc):
30                if(match(s[k],u[k]) == 0): # ３つの文字列を比較
31                    flag = 0
32                    break
33                if(match(t[k],u[k]) == 0):
34                    flag = 0
35                    break
36                if(match(s[k],t[k]) == 0):
37                    flag = 0
38                    break
39            if(flag == 1):
40                sta = min(0,i,j) #文字列の中で一番左にある開始位置
41                en = max(aa,i+bb,j+cc) #文字列の中で一番右にある終了位置
42                minlen = min(minlen,en-sta) #更新
43    return minlen
44
45print(milen(A,B,C))

試したこと

A→B→Cの順を固定することで、AとBがくっつくようになり探索する幅が狭くなるかと考えました。
ただ、A→C→Bの順となる可能性もあるので、その両方を比較する方法を試しました。
しかし実行速度はほとんど同じでした。

修正後のコード

Python
1a = input()
2b = input()
3c = input()
4
5aa = len(a)
6bb = len(b)
7cc = len(c)
8
9lensum = aa + bb + cc # 文字列の長さの最大値
10ab = [0]*(lensum+cc+1) # 相対的位置に対して合わさるかどうかを記録
11ac = [0]*(lensum+bb+1)
12bc = [0]*(lensum+aa+1)
13
14def match(v,w): # 2つの文字を合わせられるかどうかを調べる
15    if(v != '?' and w != '?' and v != w):
16        return 0
17    else:
18        return 1
19
20def match2(A,B,k): # 2つの文字列とその相対的位置に対して合わさるかチェック
21    AA = len(A)
22    BB = len(B)
23    if(k>=AA):
24        return 1
25    elif(k<-BB):
26        return 1
27    else:
28        flg = 1
29        st = max(0,k)
30        la = min(AA,BB+k)
31        for i in range(st,la):
32            if(match(A[i],B[i-k])==0):
33                flg = 0
34                break
35        return flg
36
37#ab,ac,bcに対して計算する
38for i in range(lensum+cc+1):
39    ab[i] = match2(a,b,i-bb-cc)
40for i in range(lensum+bb+1):
41    ac[i] = match2(a,c,i-bb-cc)
42for i in range(lensum+aa+1):
43    bc[i] = match2(b,c,i-aa-cc)
44
45def milen(a,b,c):
46    minlen = lensum # 文字列の長さの最大値
47    for i in range(-bb-cc,aa+cc+1): # iが文字列Bの開始位置
48        for j in range(-bb-cc,aa+bb+1): # jが文字列Cの開始位置
49            if(ab[i+bb+cc] == 0): 
50                continue
51            elif(ac[j+bb+cc] == 0):
52                continue
53            elif(j-i+aa+cc < 0 or j-i+aa+cc >= lensum+aa+1): #BとCが離れすぎている場合を除く
54                continue  
55            elif(bc[j-i+aa+cc] == 0):
56                continue   
57            else:
58                sta = min(0,i,j) #文字列の中で一番左にある開始位置
59                en = max(aa,i+bb,j+cc) #文字列の中で一番右にある終了位置
60                minlen = min(minlen,en-sta) #更新
61    return minlen
62
63print(milen(a,b,c))