blob: 4c701b6918574df329fd8d20672e2ae9befcf67c (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
require 'pp'
def lcs(s: , t: )
#matrix = [ [0] * (t.size + 1) ] * (s.size + 1)
matrix = Array.new(s.size + 1) { Array.new(t.size + 1, 0) }
(s.size - 1).downto(0) do |i|
(t.size - 1).downto(0) do |j|
if s[i] == t[j]
matrix[i][j] = 1 + matrix[i+1][j+1]
else
matrix[i][j] = [matrix[i][j+1], matrix[i+1][j]].max
end
end
end
# backtracking from 0, 0. follow the matches
result = ""
i, j = 0, 0
until matrix[i][j] <= 0
if s[i] == t[j]
result << s[i]
i += 1
j += 1
else
if matrix[i][j + 1] > matrix[i + 1][j]
j+=1
else
i+=1
end
end
end
result
end
PP.pp lcs(s: "GGCACCACG", t: "ACGGCGGATACG")
|
