Longest Common Subsequence (dynamic)

__author__ = 'DMG'

def LongestCommonSubsequence(first, second):

    dynMatrix = [[0 for x in range(len(second) + 1)] for x in range(len(first) + 1)]

    for i in xrange(1, len(first) + 1):
        for j in xrange(1, len(second) + 1):
            if first[i - 1] == second[j - 1]:
                dynMatrix[i][j] = min(dynMatrix[i][j - 1], dynMatrix[i - 1][j - 1]) + 1
            else:
                dynMatrix[i][j] = max(dynMatrix[i][j - 1], dynMatrix[i - 1][j])

    """
    for i in range(len(first) + 1):
        for j in range(len(second) + 1):
            print " " + str(dynMatrix[i][j]),
        print
    """

    lista = []

    i = j = 0
    while j < len(second) + 1:
        while i < len(first):
            if dynMatrix[i + 1][j + 1] != dynMatrix [i][j]:
                lista.append(i)
                print first[i] + " " + second[i] + " " + first[j] + " " + second[j]
                #print lista
                j = j + 1
                currentI = i + 1

            i = i + 1

            if i == len(first):
                j = j + 1
                i = currentI

    print lista


LongestCommonSubsequence("GTTCCTAATA", "CGATAATTGAGA")