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