Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A Ruby port of a solution to the Longest common subsequence problem : https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.