#!/usr/bin/env python3

def zarovnej(s1, s2):
    # jeden z řetězců se vyčerpal (nebo oba)
    if s1 == '':
        l = len(s2)
        return -1 * l, [['-' * l, s2]]
    elif s2 == '':
        l = len(s1)
        return -1 * l, [[s1, '-' * l]]
    # z obou řetězců ještě něco zbývá
    else:
        # možnost 1: ABC nebo ABC
        #            AEF      DEF
        m1_ohodnocení, m1_ss = zarovnej(s1[1:], s2[1:])
        #print(m1_ss)
        if s1[0] == s2[0]:
            m1_ohodnocení += 1
        else:
            m1_ohodnocení -= 1
        m1 = m1_ohodnocení, [[s1[0] + seq1, s2[0] + seq2] for seq1, seq2 in m1_ss]
        # možnost 2: ABC
        #            -DEF
        m2_ohodnocení, m2_ss = zarovnej(s1[1:], s2)
        m2 = -1 + m2_ohodnocení, [[s1[0] + seq1, '-' + seq2] for seq1, seq2 in m2_ss]
        # možnost 3: -ABC
        #            DEF
        m3_ohodnocení, m3_ss = zarovnej(s1, s2[1:])
        m3 = -1 + m3_ohodnocení, [['-' + seq1, s2[0] + seq2] for seq1, seq2 in m3_ss]
        # výběr lepší větve výpočtu
        xs = [m1, m2, m3]
        maximum = max(xs)[0]
        kandidáti = [x for x in sorted(xs) if x[0] == maximum]
        kolekce = []
        for x in kandidáti:
            kolekce.extend(x[1])
        return maximum, kolekce

xs = zarovnej('GAAAAAATCC', 'GAATGAATCC')      # (6, [['GAAAAAATCC', 'GAATGAATCC']]) za asi 18 vteřin
print(xs)