lcs.rb

def lcs(first, second)
  return nil if first.nil? || second.nil?
 
  x, xs, y, ys = first[0..0], first[1..-1], second[0..0], second[1..-1]
  if x == y
    x + lcs(xs, ys)
  else
    [lcs(first, ys), lcs(xs, second)].max_by {|x| x.size}
  end
end

puts lcs('ABCDAFvvB', 'ACBCFvcB')