Longest Common Sequence

# Two functions to identify the longest common sequence between two strings


def LCS1(x, y) :

    m = len(x)
    n = len(y)

    longestMatch = ''           # the longest common sequence found (yet)

    for d in xrange(1-n, m) :   # we browse the matrix intersection of x and y along its diagonals : d = i-j

        iMin = max(0, d)
        iMax = min(m, n+d)
        match = ''              # any common sequence currently going on

        for i in xrange(iMin, iMax) :
            j = i-d
            if x[i] == y[j] :
                match += x[i]                           # if a common sequence is going on we fill up 'match'
            else :
                if len(match) > len(longestMatch) :     # otherwise we check if a long enough common sequence just ended
                    longestMatch = match
                match = ''                              # and we reset 'match'

        if len(match) > len(longestMatch) :
            longestMatch = match                        # in case there was a common sequence at the end of this diagonal

    return longestMatch


def LCS2(x,y) :

    m = len(x)
    n = len(y)

    longestMatch = ''           # the longest common sequence found (yet)

    for i in xrange(m) :
        for j in xrange(n) :    # we browse the matrix intersection of x and y along its rows and columns
            k = 0
            match = ''
            while i+k < m and j+k < n and x[i+k] == y[j+k] :    # from our current position we follow the diagonal to try and find a common sequence, if any
                match += x[i+k]
                k += 1
            if k > len(longestMatch) :
                longestMatch = match

    return longestMatch