15.4-2.js

// 15.4-1

var x = [null, 1, 0, 0, 1, 0, 1, 0, 1]
var y = [null, 0, 1, 0, 1, 1, 0, 1, 1, 0]

function lcs_length(x, y) {
    var m = x.length - 1
    var n = y.length - 1

    var b = []
    var c = []

    for (var i = 1; i <= m; i++) {
        c[i] = [0]
    }

    c[0] = []
    for (var j = 0; j <= n; j++) {
        c[0][j] = 0
    }

    for (var i = 1; i <= m; i ++) {
        b[i] = []
        for (var j = 1; j <= n; j ++) {
            if (x[i] == y[j]) {
                c[i][j] = c[i - 1][j - 1] + 1
                b[i][j] = "↖"
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j]
                b[i][j] = "↑"
            } else {
                c[i][j] = c[i][j - 1]
                b[i][j] = "←"
            }
        }
    }

    return [b, c]
}

var b, c
;(function(vals){
    b = vals[0]
    c = vals[1]
})(lcs_length(x, y))
console.log(b)
console.log(c)

// 15.4-2

function lcs(c, x, y) {
    var i = x.length - 1
    var j = y.length - 1

    var dest = []

    while (i > 0 && j > 0) {
        if (x[i] == y[j]) {
            dest.unshift(x[i])
            i --; j --
        } else if (c[i - 1][j] >= c[i][j - 1]) {
            i --
        } else {
            j --
        }
    }

    return dest
}

console.log(lcs(c, x, y))