最長共通部分列(Longest Common Subsequence; LCS)を求めてみる

Python 30分プログラム

30分プログラム、その774。最長共通部分列(Longest Common Subsequence; LCS)を求めてみました。
LCSが何かについては最長共通部分列問題 (Longest Common Subsequence) - naoyaのはてなダイアリーに詳しく書かれているので、そちらを参照してください。
動的計画法が有効だと聞きかじったので、ハッシュテーブルを使って一度計算した値を保存するようにしました。ホントはmemoize関数とか作るのが格好いいんだろうけどなー。

使い方

>>> lcs("ABCBDAB","BDCABA")
"BDAB"

ソースコード

#! /usr/bin/python
# -*- mode:python; coding:utf-8 -*-

def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y

table = { ("","") : "" }

def lcs(xs,ys):
    if (xs,ys) in table:
        return table[(xs,ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1],ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1],ys),
                    lcs(xs,ys[:-1]))
    table[(xs,ys)] = ret
    return ret

print lcs("ABCBDAB","BDCABA")

参考