最長共通部分列（Ruby）

文字列の「部分列」とは、文字列から任意の文字を取り除いたものをいう。文字列 X と Y があって、文字列 Z が X と Y 両方の部分列になっている場合、Z を X, Y の「共通部分列」という。共通部分列の最長のものが、「最長共通部分列」である。たとえば文字列 CATCGA と GTACCGTCA の最長共通部分列は CTCA である。

これを Ruby で求めるプログラムを書きました。
LCS.rb

def compute_LCS_table(x, y)
  l = Array.new(x.length + 1) {Array.new(y.length + 1, 0)}
  1.upto(x.length) do |i|
    1.upto(y.length) do |j|
      l[i][j] = if x[i - 1] == y[j - 1]
        l[i - 1][j - 1] + 1
      else
        a, b = l[i][j - 1], l[i - 1][j]
        (a > b) ? a : b
      end
    end
  end
  l
end

def assemble_LCS(x, y, l, i, j)
  return "" if l[i][j].zero?
  if x[i - 1] == y[j - 1]
    assemble_LCS(x, y, l, i - 1, j - 1) + x[i - 1]
  elsif l[i][j - 1] > l[i - 1][j]
    assemble_LCS(x, y, l, i, j - 1)
  else
    assemble_LCS(x, y, l, i - 1, j)
  end
end


x, y = "CATCGA", "GTACCGTCA"
l = compute_LCS_table(x, y)
puts assemble_LCS(x, y, l, x.length, y.length)    #=>CTCA

ここで最初に compute_LCS_table で求めている l[i][j] は、文字列 x[0..(i - 1)], y[0..(j - 1)] の最長共通部分列の長さです。これは動的計画法で求めています。それから assemble_LCS で実際の最長共通部分列を求め直しています。
　