Longest Common Subsequence

gistfile1.rb

class LongestCommonSequence
  def initialize(str1, str2)
    @str1 = str1
    @str2 = str2
    @cached_lcs_for_points = {}
  end

  def get
    get_lcs(0, 0)
  end

  private

  def get_lcs(x, y)
    @cached_lcs_for_points[:"#{x}-#{y}"] ||= begin
      if @str1[x].nil? || @str2[y].nil?
        ''
      elsif @str1[x] == @str2[y]
        @str1[x] + get_lcs(x + 1, y + 1)
      else
        longest(get_lcs(x, y + 1), get_lcs(x + 1, y))
      end
    end
  end

  def longest(str1, str2)
    str1.size >= str2.size ? str1 : str2
  end
end

File.read(ARGV[0]).each_line do |line|
  str1, str2 = line.strip.split(';')
  puts LongestCommonSequence.new(str1, str2).get
end