Longest common subsequence problem

lcs.rb

x, y = "CATCGA", "GTACCGTCA"

table = [ ]
(0..x.length).each { table << row = [ ];  (0..y.length).each { row << 0 } }
x.chars.each_with_index { |xc, xi|
  y.chars.each_with_index { |yc, yi|
    pxv = table[xi][yi + 1]
    pyv = table[xi + 1][yi]
    pvg = pxv > pyv ? pxv : pyv
    pvl = pxv <= pyv ? pxv : pyv
    table[xi + 1][yi + 1] = (xc == yc ? pvl + 1 : pvg)
  }
}
table.shift
table.each { |row| row.shift }

puts "   #{y.chars.join ", "}"
table.each_with_index { |row, i| puts "#{x[i]}: #{row.join ", "}" }
lcs_l = table[table.size - 1][table[table.size - 1].size - 1]
puts "LCS length: #{lcs_l}, #{(lcs_l / ((x.length + y.length) / 2.0)).round(2)}"

lcs = [ ]
assemble = lambda { |x, y, table, i, j|
  return if j < 0 || i < 0
  return if table[i][j] == 0
  if x[i] == y[j]
    lcs << x[i]
    return assemble.call x, y, table, i - 1, j - 1
  end
  if table[i][j - 1] >= table[i - 1][j]
    assemble.call x, y, table, i, j - 1
  else
    assemble.call x, y, table, i - 1, j
  end
}
assemble.call x, y, table, x.length - 1, y.length - 1

puts "lcs: #{lcs.reverse.join}"