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)