Problem p02745 (python)

Fixed submission:
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()

Buggy submission (verdict: Runtime Error):
import sys

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):
    lt = len(t)
    ls = len(s)
    l = [0]*lt
    for i in range(len(t)):
        j = 0
        while j < ls and i+j < lt and (s[j] == t[i+j] or s[j] == ques or t[i+j] == ques):
            j += 1
        l[i] = j
    return l

def main():
    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()))

    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):
        lli = len(l[i])
        for j in range(3):
            if i == j: continue
            k = 3-i-j
            llj = len(l[j])
            llk = len(l[k])
            li = [ii for ii in range(lli) if g[j][i][ii] >= min(lli - ii, llj)]
            lj = [ii for ii in range(lli) if g[k][j][ii] >= min(llj - ii, llk)]
            lk = [ii for ii in range(lli) if g[k][i][ii] >= min(lli - ii, llk)]
            if li:
                c = max(lli, min(li) + llj + llk)
                if ans > c: ans = c
            for ii in li:
                for jj in lj:
                    kk = ii + jj
                    if kk >= lli or g[k][i][kk] >= min(lli - kk, llk):
                        c = max(lli, ii + llj, kk + llk)
                        if ans > c: ans = c
            for ii in li:
                for kk in lk:
                    if kk < ii + len(l[j]): continue
                    c = max(lli, ii + llj, kk + llk)
                    if ans > c: ans = c
    print(ans)

if __name__ == "__main__":
    ques = ord('?')
    main()

Buggy submission (verdict: Runtime Error):
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, len(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()

Buggy submission (verdict: Runtime Error):
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):
            for j in range(i, 3):
                for k in range(len(s[i])):
                    ok = True
                    for ni in range(k, len(s[i])):
                        nj = ni - k
                        if nj > len(s[j]):
                            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()

Buggy submission (verdict: Runtime Error):
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]*3 for _ in range(3)] for _ in range(n)]
    ans = n*3
    for s in permutations(ss):
        for i in range(3):
            for j in range(i, 3):
                for k in range(len(s[i])):
                    ok = True
                    for ni in range(k, len(s[i])):
                        nj = ni - k
                        if nj > len(s[j]):
                            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()