codepad

Language:

def longest_common_subsequence(A, B):
    """Determine how long the longest common subsequence of A and B are, then
       reconstruct it."""
    
    # create a matrix that will hold the values of a and b
    range_a = range(0, len(A)+1)
    range_b = range(0, len(B)+1)
    matrix = [[0 for j in range_a] for i in range_b]
    
    # go through each character in B
    for i in range(1, len(B)+1):
        
        # go through the characters in A for each character in B
        for j in range(1, len(A)+1):
            
            # compare the current character of B to that of A
            if B[i-1] is A[j-1]:
                matrix[i][j] = matrix[i][j-1]+1
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1])
    
    print "Length of subsequence:", matrix[i][j]
    
    # reconstruct the subsequence from the end to the beginning
    sub_sequence = ""
    while i > 0 and j > 0:  
                
        # we've found a matching character, add it to the subsequence
        if B[i-1] is A[j-1]:
            sub_sequence = A[j-1] + sub_sequence
            i = i-1
            j = j-1
        
        # we haven't found one, either move left or up, depending on the
        # larger value
        else:
            # move up
            if matrix[i-1][j] > matrix[i][j-1]:
                i = i-1
            
            # move left, also the default when (i-1,j)==(i,j-1)
            else:
                j = j-1
    
    print "The subsequence is:", sub_sequence

longest_common_subsequence("gattaca", "atrtic")

Private [?]

Run code