lcs for slyphon

lcs.py

#!/usr/bin/env python3

def lcs_recursive(a, b):
    if a is "" or b is "":
        return ""
    else:
        x = lcs_recursive(a[1:], b)
        y = lcs_recursive(a, b[1:])
        z = a[0] + lcs_recursive(a[1:], b[1:]) if a[0] == b[0] else ""
        return max([x, y, z], key=lambda x: len(x))

def lcs(a, b):
    return lcs_reconstruct(lcs_matrix(a, b), a, b)

def lcs_matrix(a, b):
    matrix = [ [ 0 for _ in range(len(a) + 1) ] for _ in range(len(b) + 1) ]

    for i in range(len(a) - 1, -1, -1):
        for j in range(len(b) - 1, -1, -1):
            (_, right, down, diag) = neighbors(matrix, i, j)
            matrix[j][i] = max(1 + diag if a[i] == b[j] else 0, right, down)

    return matrix

def lcs_reconstruct(matrix, a, b):
    result = []
    j = 0
    i = 0

    while j < len(b) and i < len(a):

        (here, right, down, diag) = neighbors(matrix, i, j)

        if right == down == diag == (here - 1):
            result.append(a[i])
            i += 1
            j += 1

        elif down == here:
            j += 1

        elif right == here:
            i += 1

    return ''.join(result)

def neighbors(m, i, j):
    return (m[j][i], m[j][i+1], m[j+1][i], m[j+1][i+1])