src/dp/lcs.cr

• View this file on GitHub
• Last update: 2022-04-16 07:49:21+00:00

Verified with

• test/dp/lcs_test.cr

Code

module DP
  extend self

  def lcs(s, t)
    n, m = s.size, t.size
    dp = Array.new(m + 1, 0)
    n.times do |i|
      dp2 = dp.dup
      m.times do |j|
        dp2[j + 1] = {dp2[j + 1], dp[j] + 1}.max if s[i] == t[j]
        dp2[j + 1] = {dp2[j + 1], dp2[j]}.max
      end
      dp = dp2
    end
    dp[m]
  end
end

module DP
  extend self

  def lcs(s, t)
    n, m = s.size, t.size
    dp = Array.new(m + 1, 0)
    n.times do |i|
      dp2 = dp.dup
      m.times do |j|
        dp2[j + 1] = {dp2[j + 1], dp[j] + 1}.max if s[i] == t[j]
        dp2[j + 1] = {dp2[j + 1], dp2[j]}.max
      end
      dp = dp2
    end
    dp[m]
  end
end

Back to top page