Class: Algorithmable::Cups::LongestCommonSubSequence

Inherits:
Object
  • Object
show all
Defined in:
lib/algorithmable/cups/longest_common_subsequence.rb

Instance Method Summary collapse

Instance Method Details

#find(a, b) ⇒ Object

>> a = “aaaaabbbb34354354345” >> b = “abbb34aaabbbb” >> find(a, b)

> “aaaabbbb”

See Also:



12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
# File 'lib/algorithmable/cups/longest_common_subsequence.rb', line 12

def find(a, b)
  max_len = Array.new(a.size + 1, 0)
  max_len.map! { Array.new(b.size + 1, 0) }

  (a.size - 1).downto(0) do |i|
    (b.size - 1).downto(0) do |j|
      if a[i] == b[j]
        max_len[i][j] = 1 + max_len[i + 1][j + 1]
      else
        max_len[i][j] = [max_len[i + 1][j], max_len[i][j + 1]].max
      end
    end
  end

  res = ''
  i = 0
  j = 0
  while max_len[i][j] != 0 && i < a.size && j < b.size
    if a[i] == b[j]
      res << a[i]
      i += 1
      j += 1
    else
      if max_len[i][j] == max_len[i + 1][j]
        i += 1
      else
        j += 1
      end
    end
  end
  res
end