去年LCS長を求めるプログラムをRubyで書いた。
https://hai3.net/blog/ruby-lcs2/
今回は、LCSそのものを求めるプログラムを書いた。
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を求める。
'point'.lcs('font')
この時のlcs_lenとlcs_vecは次のようになっている。
lcs_vecの右下から、経路を戻っていくとLCSを求めることができる。
これをやっているのがrestore_lcsメソッド。
# 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"]]