"""
    Longest Common Sunsequence
    --------------------------
    Implements the dynamic programming solution to the longest common
    subsequence algorithm.

    Pseudo Code:
    http://en.wikipedia.org/wiki/Longest_common_subsequence_problem
"""


def build_lengths_matrix(str1, str2):
    """
    XXX: Needs documentation written.
    """
    matrix = [[0 for j in range(len(str2)+1)] for i in range(len(str1)+1)]
    for i, x in enumerate(str1):
        for j, y in enumerate(str2):
            if x == y:
                matrix[i+1][j+1] = matrix[i][j] + 1
            else:
                matrix[i+1][j+1] = max(matrix[i+1][j], matrix[i][j+1])
    return matrix


def read_from_matrix(matrix, str1, str2):
    """
    XXX: Needs documentation written.
    """
    result = ""
    i, j = len(str1), len(str2)
    while i != 0 and j != 0:
        if matrix[i][j] == matrix[i-1][j]:
            i -= 1
        elif matrix[i][j] == matrix[i][j-1]:
            j -= 1
        else:
            result += str1[i-1]
            i -= 1
            j -= 1
    return result[::-1]


def lcs(str1, str2):
    """
    XXX: Needs documentation written.
    """
    lengths = build_lengths_matrix(str1, str2)
    return read_from_matrix(lengths, str1, str2)

@@ -18,17 +18,17 @@
 ommon Su
-n
+b
 sequence

Update lcs.py