Реализации алгоритмов/Наибольшая общая подпоследовательность: различия между версиями
Содержимое удалено Содержимое добавлено
Строка 96:
lcs(x = 'dggfgffegsss345265', y = 'vdfspkddssf4563')
#=> "dfsss456"
'''ещё один вариант:'''
def lcs(x, y)
dp = Array.new(x.length + 1){Array.new(y.length + 1){''}}
x.each_char.with_index do |c, i|
y.each_char.with_index do |d, j|
result = [dp[i][j], dp[i][j + 1], dp[i + 1][j]].max_by(&:length)
if c == d
result = dp[i][j] + c
end
dp[i + 1][j + 1] = result
end
end
dp[-1][-1]
end
lcs(x = 'dggfgffegsss345265', y = 'vdfspkddssf4563')
</source>
| |||