去年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"]] |