Algorightms homework :(

lcs.coffee

lcs_length = (x,y) -> #1 indexed arrays
  m = x.length - 1
  n = y.length - 1 
  c = []
  b = []
  for i in [0..m]
    c[i] = []
    b[i] = []
    c[i][0] = 0
  for j in [1..n]
    c[0][j] = 0
  for i in [1..m]
    for j in [1..n]
      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] = "←"
  
  str  = ["<table id='lcs' border=1>"]
  str.push "<tr>"
  str.push "<td></td>"
  str.push "<td>j</td>"
  for i in [0..n]
    str.push "<td>#{i}</td>"
  str.push "</tr>"
  str.push "<tr>"
  str.push "<td>i</td>"
  str.push "<td>c[i,j]</td>"
  for i in [0..n]
    if i is 0
      str.push "<td>yj=</td>"
    else
      str.push "<td>#{y[i]}</td>"
  str.push "</tr>"
  
  for i in [0..m]
    str.push "<tr>"
    str.push "<td>#{i}</td>"
    if i is 0
      str.push "<td>#{i}</td>"
    else
      str.push "<td>#{x[i]}</td>"
    for j in [0..n]
      str.push "<td>#{c[i][j]} #{b[i][j]}</td>"
    str.push "</tr>" 
    $('#lcs').remove()
    $(document.body).append str.join "" 
  return [c,b]
  
construct_lcs = (b, x, i, j) ->
  if i is 0 or j is 0
    return
  if b[i][j] == "↖"
    construct_lcs b, x, i-1, j-1
    console.log x[i]
  else if b[i][j] == "↑"
    construct_lcs b, x, i-1, j
  else
    construct_lcs b, x, i, j-1


lcs_length " ABCBDAB".split(""), " BDCABA".split("")