LCS Algorithm
123456789101112131415161718192021222324252627
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)
Ruby
INFO