class Algorithmable::Cups::LongestCommonSubSequence

Public Instance Methods

find(a, b) click to toggle source

@see en.wikipedia.org/wiki/Longest_common_subsequence_problem

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

> “aaaabbbb”

# 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