aligns two strings

    >>> print(*align('pharmacy', 'farmácia', gap='_'), sep='\\n')
    pharmac_y
    _farmácia

    >>> print(*align('advantage', 'vantagem', gap='_'), sep='\\n')
    advantage_
    __vantagem

def align(s1, s2, gap=' ', eq=operator.eq):
    '''aligns two strings

    >>> print(*align('pharmacy', 'farmácia', gap='_'), sep='\\n')
    pharmac_y
    _farmácia

    >>> print(*align('advantage', 'vantagem', gap='_'), sep='\\n')
    advantage_
    __vantagem

    '''
    # first we compute the dynamic programming table
    m, n = len(s1), len(s2)
    table = []  # the table is extended lazily, one row at a time
    row = list(range(n+1))  # the first row is 0, 1, 2, ..., n
    table.append(list(row))  # copy row and insert into table
    for i in range(m):
        p = i
        row[0] = i+1
        for j in range(n):
            t = 0 if eq(s1[i], s2[j]) else 1
            p, row[j+1] = row[j+1], min(p+t, row[j]+1, row[j+1]+1)
        table.append(list(row))  # copy row and insert into table
    # now we trace the best alignment path from cell [m][n] to cell [0],[0]
    s1_, s2_ = '', ''

    i, j = m, n
    while i != 0 and j != 0:
        _, i, j, s1_, s2_ = min(
            (table[i-1][j-1], i-1, j-1, s1[i-1]+s1_, s2[j-1]+s2_),
            (table[i-1][j], i-1, j, s1[i-1]+s1_, gap+s2_),
            (table[i][j-1], i, j-1, gap+s1_, s2[j-1]+s2_)
        )
    if i != 0:
        s1_ = s1[:i]+s1_
        s2_ = gap*i+s2_
    if j != 0:
        s1_ = gap*j+s1_
        s2_ = s2[:j]+s2_
    return s1_, s2_