久しぶりに自分のブログにアクセスしたら「データベース接続エラー」になってた・・。
最近ブログ放置していた、というのも、RailsとかJSとかのwebネタは社内の情報共有場所に投稿してしまうので、この個人ブログに重複して書くのもうんこだなーと思ってしまって。
なのでブログの方向はもうちょっと趣味寄りにしたい。でもまた６ヶ月ぐらい放置するかも。
それはそうと、LCS長問題。
LCS問題がどんなものかはwikipediaでどうぞ。
wikipediaのように厳密を蛋白に書かれるとよくわからないんだけれど、例を挙げると少しわかるかもしれない。
- abc と aec の LCS は ac
- point と font の LCS は ont
- bug と debug の LCS は bug
要は、各文字列から間に何か入っていても良いから同じ順序で出てくる文字の列がLCS。
このLCSの長さを求める問題は、ナップザック問題と並んで動的計画法の有名問題となっているらしく、今回はRubyでそれを解いてみた。
コードは以下。
# input
s1 = gets.chomp
s2 = gets.chomp
# initialize
dp = Array.new(s1.size + 1).map { Array.new(s2.size + 1, 0) }
# resolve
s1.size.times do |i|
s2.size.times do |j|
if s1[i] == s2[j]
dp[i+1][j+1] = dp[i][j] + 1
else
dp[i+1][j+1] = [dp[i+1][j], dp[i][j+1]].max
end
end
end
# output
puts dp[s1.size][s2.size]
解説。
dpに記録しているものは、s1からi文字使った場合とs2からj文字使った場合のLCS長
s1[i]とs2[j]が一致する場合は、LCS長はs1[i]とs2[j]を使わなかったものより１つ大きくなるはずで、一致しない場合は、s1[i]とs2[j]のどちらかを使った場合のLCS長の大きい方となる。
このプログラムをトレースする。
入力 s1 が point、入力 s2 が font だった時のループは
i=0, j=0 の時 point font は一致しないので dp[1][1] は 0
i=0, j=1 の時 point font は一致しないので dp[1][2] は 0
i=0, j=2 の時 point font は一致しないので dp[1][3] は 0
i=0, j=3 の時 point font は一致しないので dp[1][4] は 0
i=1, j=0 の時 point font は一致しないので dp[2][1] は 0
i=1, j=1 の時 point font は一致するので dp[2][2] は 1
i=1, j=2 の時 point font は一致しないので dp[2][3] は 1
i=1, j=3 の時 point font は一致しないので dp[2][4] は 1
i=2, j=0 の時 point font は一致しないので dp[3][1] は 0
i=2, j=1 の時 point font は一致しないので dp[3][2] は 1
i=2, j=2 の時 point font は一致しないので dp[3][3] は 1
i=2, j=3 の時 point font は一致しないので dp[3][4] は 1
i=3, j=0 の時 point font は一致しないので dp[4][1] は 0
i=3, j=1 の時 point font は一致しないので dp[4][2] は 1
i=3, j=2 の時 point font は一致するので dp[4][3] は 2
i=3, j=3 の時 point font は一致しないので dp[4][4] は 2
i=4, j=0 の時 point font は一致しないので dp[5][1] は 0
i=4, j=1 の時 point font は一致しないので dp[5][2] は 1
i=4, j=2 の時 point font は一致しないので dp[5][3] は 2
i=4, j=3 の時 point font は一致するので dp[5][4] は 3
となり、dp[5][4]でLCS長が求まる。
