# problem 5
def prefix_size(P,Q):
    n = len(P)
    m = len(Q)
    temp = min(n,m)
    max_len = 0
    s = P
    s+=Q
    for i in range(1, temp+1):
        x1 = P[-i:]
        x2 = Q[:i]
        x3 = Q[i:]
        if x1 == x2:
            if i >= max_len:
                max_len = i
                s = P + x3
            max_len = max(max_len, i)
    return max_len, s

def shortest_superstring(A):
    count = len(A)-1
    while count:
        count-=1
        result_len = -1
        for i in range(len(A)):
            for j in range(i+1, len(A)):
                temp = prefix_size(A[i], A[j])
                if temp[0] > result_len:
                    result_len = temp[0]
                    final = temp[1]
                    p = A[i]
                    q = A[j]
                temp2 = prefix_size(A[j], A[i])
                if temp2[0] > result_len:
                    result_len = temp2[0]
                    final = temp2[1]
                    p = A[j]
                    q = A[i]
        A.append(final)
        A.remove(p)
        A.remove(q)
    return A[0]


print(shortest_superstring(["CATGC", "CTAAGT", "GCTA", "TTCA", "ATGCATC"]))
print(shortest_superstring(["ABC", "EFG", "ABCD"]))