Ex5 c-d

#!/usr/local/bin/python2.7
# encoding: utf-8
import numpy as np


def equal_letters_strings(X, Y):

    N = len(X)
    M = len(Y)

    Memory = np.zeros((N, M))

    for i in range(0, N):
        if X[i] == Y[0]:
            Memory[i][0] = 1
        else:
            Memory[i][0] = Memory[i - 1][0]

    for j in range(0, M):
        if Y[j] == X[0]:
            Memory[0][j] = 1
        else:
            Memory[0][j] = Memory[0][j - 1]

    # Preenche a matriz de memorização
    for i in range(1, N):
        for j in range(1, M):
            if X[i] == Y[j]:
                Memory[i][j] = Memory[i - 1][j - 1] + 1
            else:
                Memory[i][j] = max(Memory[i - 1][j], Memory[i][j - 1])

    for line in range(0, N):
        for column in range(0, M):
            print("%d" % Memory[line][column]),
        print

    # Agora vamos retornar a sequência comum mais longa
    i = N - 1
    j = M - 1

    seq = []
    while(i >= 0 and j >= 0):
        if i == 0:
            if Memory[0][j] == Memory[0][j - 1] + 1 and X[0] == Y[j]:
                seq.append(X[0])
            j = j - 1
        elif j == 0:
            if Memory[i][0] == Memory[i - 1][0] + 1 and X[i] == Y[0]:
                seq.append(Y[0])
            i = i - 1

        elif Memory[i][j] == Memory[i - 1][j - 1] + 1 and X[i] == Y[j]:
            seq.append(X[i])
            i = i - 1
            j = j - 1
        elif Memory[i - 1][j] > Memory[i][j - 1]:
            i = i - 1
        else:
            j = j - 1
    print
    print ("Seq mais longa: %s " % seq)

if __name__ == '__main__':
    X = ['A', 'C', 'B', 'D', 'E', 'G', 'C', 'E', 'D', 'B', 'G']
    Y = ['B', 'E', 'G', 'C', 'F', 'E', 'U', 'B', 'K']

    equal_letters_strings(X, Y)