最長共通部分列問題 (Longest Common Subsequence)

最初、最長共通部分列問題と聞いたときは、部分文字列の最長を求める問題だと思ったのですが、そうではないんですね。参考サイトを見ているうちに、なんとか題意とこの問題の意義のようなものが見えるようになってきました。

理解を深めるために、最長共通部分列問題 (Longest Common Subsequence)でPerlとPythonで書かれていたスクリプトをRubyで書いて実行してみました。

lcs.rb

実行結果

$ ruby lcs.rb ABCBDAB BDCABA
B C B A

参考サイト

• 最長共通部分列問題 (Longest Common Subsequence)
• 最長共通部分列問題 - Wikipedia