https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

longest_common_subsequence.rb

#!/usr/bin/env ruby

if ARGV.length != 2
  puts
  puts 'ERROR! This script needs exactly two strings as input. Example: '
  puts
  puts '    ruby subsequence.rb XMJYAUZ MZJAWXU'
  puts
  exit -1
end

def longest_common_subsequence string_1, string_2
  table   = []
  rows    = string_1.length
  columns = string_2.length
  output  = ''

  (rows + 1).times do |outer_index|
    table << []

    (columns + 1).times do |inner_index|
      current_value = 0

      if outer_index.zero? || inner_index.zero?
        current_value = 0
      elsif string_1[outer_index - 1] == string_2[inner_index - 1]
        current_value = table[outer_index - 1][inner_index - 1] + 1
      else
        current_value = [ table[outer_index][inner_index - 1],
                          table[outer_index - 1][inner_index] ].max
      end

      table[outer_index] << current_value
    end
  end

  while table[rows][columns] > 0 do
    if (string_1[rows - 1] == string_2[columns - 1]) && (table[rows - 1][columns - 1] + 1 == table[rows][columns])
      output = string_1[rows - 1] + output

      rows    -= 1
      columns -= 1
    elsif table[rows - 1][columns] > table[rows][columns - 1]
      rows -= 1
    else
      columns -= 1
    end
  end

  puts output
end


string_1, string_2 = ARGV[0], ARGV[1]
longest_common_subsequence string_1, string_2

__END__
XMJYAUZ MZJAWXU MJAU