compute the lcs length of 2 sequences.

lcs_length.py

import numpy

def lcs_length(X, Y):
    m, n = len(X), len(Y)
    min_len = min(m, n)
    max_len = max(m, n)
    C = numpy.zeros(shape=(2, min_len+1))
    if m == min_len:
        min_list = X
        max_list = Y
    else:
        min_list = Y
        max_list = X
    working_line = 0
    reserved_line = 1
    for i in xrange(1, max_len+1):
        working_line, reserved_line = reserved_line, working_line
        for j in xrange(1, min_len+1):
            if max_list[i-1] == min_list[j-1]:
                C[working_line, j] = C[reserved_line, j-1] + 1
            else:
                C[working_line, j] = max(C[working_line, j-1], C[reserved_line, j])
    return C[working_line, min_len]