test/dp/lcs_test.cr

View this file on GitHub
Last update: 2021-08-04 13:11:57+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C

Depends on

src/dp/lcs.cr

Code

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C
require "../../src/dp/lcs"
read_line.to_i.times do
  s = read_line
  t = read_line
  puts DP.lcs(s, t)
end

# verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_10_C
# require "../../src/dp/lcs"
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

read_line.to_i.times do
  s = read_line
  t = read_line
  puts DP.lcs(s, t)
end