LCS Algorithm

def lcs(x, y)
	def get(vals, i, j)
		i < 0 || j < 0 ? '' : vals[i][j]
	end
	vals = x.size.times.map do
	    [''] * y.size
	end
	x.size.times do |i|
		y.size.times do |j|
			if x[i] == y[j]
				vals[i][j] = get(vals, i - 1, j - 1) + x[i]
			else
				vals[i][j] = [get(vals, i - 1, j), get(vals, i, j - 1)].max_by(&:size)
			end
		end
	end
	vals[x.size - 1][y.size - 1]
end
def genRandomStr
	(0..100).map do
	    (65 + rand(26)).chr
	end.join
end
str1 = genRandomStr
str2 = genRandomStr
puts str1,str2
puts lcs(str1, str2)