Longest common subsequence

lcs.py

# longest common subsequence

def lcs(x, y):
    """ returns longest common sequence length, exponential runtime complexity """
    if len(x) == 0 or len(y) == 0:
        return 0
    elif x[-1] == y[-1]:
        return lcs(x[:-1], y[:-1]) + 1
    else:
        return max(lcs(x[:-1], y),
                   lcs(x, y[:-1]))


def print_c(c):
    for row in c:
        for col in row:
            print(f'{col:2}', end=" ")
        print()
    print()


def dynamic_lcs(x, y):
    """ returns longest common sequence length, linear runtime complexity """
    m = len(x) + 1
    n = len(y) + 1
    c = [[-1 for i in range(n)] for j in range(m)]
    b = [[0 for i in range(n)] for j in range(m)]

    # base cases
    for i in range(m):
        c[i][0] = 0
    for j in range(n):
        c[0][j] = 0

    # compute sub problems
    for i in range(1, m):
        for j in range(1, n):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = 1  # up-left arrow
            else:
                if c[i - 1][j] >= c[i][j - 1]:
                    c[i][j] = c[i - 1][j]
                    b[i][j] = 2  # up arrow
                else:
                    c[i][j] = c[i][j - 1]
                    b[i][j] = 3  # left arrow

    def _print_lcs(i, j):
        if i == 0 or j == 0:
            return
        if b[i][j] == 1:  # up-left arrow
            _print_lcs(i - 1, j - 1)
            print(x[i - 1], end=" ")
        elif b[i][j] == 2:  # up arrow
            _print_lcs(i - 1, j)
        else:  # left arrow
            _print_lcs(i, j - 1)

    print_c(c)
    _print_lcs(len(x), len(y))


if __name__ == '__main__':
    x = ['a', 'b', 'c', 'b', 'd', 'a', 'b']
    y = ['b', 'd', 'c', 'a', 'b', 'a']
    # print(lcs(x, y))
    dynamic_lcs(x, y)

lcs.rkt

#lang racket
(define (lcs xs ys)
  (cond ((or (empty? xs) (empty? ys)) 0)
        ((equal? (first xs) (first ys)) (+ (lcs (rest xs) (rest ys)) 1))
        (else (max (lcs (rest xs) ys)
                   (lcs ys (rest xs))))))

(lcs '("a" "b" "c" "b" "d" "a" "b")
     '("b" "d" "c" "a" "b"))

 0  0  0  0  0  0  0 
 0  0  0  0  1  1  1 
 0  1  1  1  1  2  2 
 0  1  1  2  2  2  2 
 0  1  1  2  2  3  3 
 0  1  2  2  2  3  3 
 0  1  2  2  3  3  4 
 0  1  2  2  3  4  4 

b c b a