カテゴリー別アーカイブ: アルゴリズムイントロダクション

RubyでLCSを求める

ruby, アルゴリズムイントロダクション
このエントリーをはてなブックマークに追加

去年LCS長を求めるプログラムをRubyで書いた。
http://hai3.net/blog/2014/09/17/ruby-lcs/

今回は、LCSそのものを求めるプログラムを書いた。

1
2
3
4
5
6
7
8
9
10
11
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
class String
  def lcs(target)
    lcs_len = Array.new(size + 1) { Array.new(target.size + 1) { 0 } }
    lcs_vec = Array.new(size + 1) { Array.new(target.size + 1) }

    each_char.with_index(1) do |c1, i|
      target.each_char.with_index(1) do |c2, j|
        if c1 == c2
          lcs_len[i][j] = lcs_len[i-1][j-1] + 1
          lcs_vec[i][j] = 'LU'
        elsif lcs_len[i-1][j] >= lcs_len[i][j-1]
          lcs_len[i][j] = lcs_len[i-1][j]
          lcs_vec[i][j] = 'U'
        else
          lcs_len[i][j] = lcs_len[i][j-1]
          lcs_vec[i][j] = 'L'
        end
      end
    end

    restore_lcs(lcs_vec, size, target.size, '')
  end

  private

  def restore_lcs(lcs_vec, i, j, result)
    return if i == 0 || j == 0

    case lcs_vec[i][j]
    when 'LU'
      restore_lcs(lcs_vec, i-1, j-1, result).to_s + self[i-1]
    when 'U'
      restore_lcs(lcs_vec, i-1, j, result)
    else
      restore_lcs(lcs_vec, i, j-1, result)
    end
  end
end

LCSの求め方は大体前の記事と同じだけれど、違うのはlcs_vecという配列にLCSの復元経路を入れているところ。
例えば、次のようにpointとfontのLCSを求める。

1
'point'.lcs('font')

この時のlcs_lenとlcs_vecは次のようになっている。
lcs_vecの右下から、経路を戻っていくとLCSを求めることができる。
これをやっているのがrestore_lcsメソッド。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# lcs_len
[[0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 1, 1, 1],
 [0, 0, 1, 1, 1],
 [0, 0, 1, 2, 2],
 [0, 0, 1, 2, 3]]

# lcs_vec
[[nil, nil, nil, nil, nil],
 [nil, "U", "U", "U", "U"],
 [nil, "U", "LU", "L", "L"],
 [nil, "U", "U", "U", "U"],
 [nil, "U", "U", "LU", "L"],
 [nil, "U", "U", "U", "LU"]]