🐸

[鉄則A20] LCS (最長共通部分列)

2024/03/29に公開

Ruby

類似度がわかる最長共通部分列問題。

問題の要約

二つの文字列がどれだけ似ているか？

たとえば ab と axb だと 2 文字分同じ並びで一致するので答えは 2 になる。

解説の模範解答風 (AC)

811 ms

A = gets.strip  # => "mynavi"
B = gets.strip  # => "monday"
H = A.size      # => 6
W = B.size      # => 6
dp = Array.new(H.next) { Array.new(W.next) }
dp[0][0] = 0
(0..H).each do |y|
  (0..W).each do |x|
    u  = dp[y - 1][x - 0]   # 上
    l  = dp[y - 0][x - 1]   # 左
    lu = dp[y - 1][x - 1]   # 左上
    v = nil
    case
    when y >= 1 && x >= 1 && A[y - 1] == B[x - 1]  # 同じ場合
      v = [u, l, lu + 1].max  # 上・左・左上+1 の大きいもの
    when y >= 1 && x >= 1
      v = [u, l].max          # 同じでなければ上と左の大きい方
    when y >= 1               # 左端は
      v = u                   # 上から下にコピー
    when x >= 1               # 一行目は
      v = l                   # 左から右にコピー
    end
    if v
      dp[y][x] = v
    end
  end
end
p dp[H][W]      # => 3

	m	o	n	d	a	y
-	0	0	0	0	0	0
m	1	1	1	1	1	1
y	1	1	1	1	1	2
n	1	1	2	2	2	2
a	1	1	2	2	3	3
v	1	1	2	2	3	3
i	1	1	2	2	3	3

縦横で文字が一致したとき左上の値を +1 しているのがわかる。

リファクタリング後 (AC)

772 ms

A = gets.strip  # => "mynavi"
B = gets.strip  # => "monday"
H = A.size      # => 6
W = B.size      # => 6
dp = Array.new(H.next) { Array.new(W.next, 0) } # 0 で初期化しておくと後が楽になる
(1..H).each do |y|
  (1..W).each do |x|
    u  = dp[y - 1][x - 0]           # 上
    l  = dp[y - 0][x - 1]           # 左
    lu = dp[y - 1][x - 1]           # 左上
    if A[y - 1] == B[x - 1]         # 同じ場合
      dp[y][x] = [u, l, lu + 1].max # 上・左・左上+1 の大きいもの
    else
      dp[y][x] = [u, l].max         # 同じでなければ上と左の大きい方
    end
  end
end
p dp[H][W]      # => 3

dp の一行目と左端は 0 と決まっているのでループ内で埋める必要はない。dp を 0 で初期化しておけばループは 1 から開始できるため x >= 1 と y >= 1 の条件を捨てられる。

要点

一行目と左端は 0 にしておくとコードが簡潔になる
一致したとき「左」と「上」と「左上＋1」の大きい方を書く
一致しないとき「左」と「上」の大きい方を書く

問題の要約

解説の模範解答風 (AC)

リファクタリング後 (AC)

要点

Discussion