最長共通部分列

部分列 (Subsequence) は系列のいくつかの要素を取り出してできた系列のこと。二つの系列の共通の部分列を共通部分列 (Common Subsecuence)と呼ぶ。共通部分列のうち、もっとも長いものを最長共通部分列 (Longest Common Subsequence, LCS) と呼ぶ。

• X =
• Y =

という二つの系列から得られる LCS は

で、その長さは 4 である。長さ 2 の の長さ 3 の なども共通部分列だが、最長ではないのでこれらは LCS ではない。LCS は最長であれば位置はどこでも良いので、この場合 も LCS である。

LCS は動的計画法 (Dynamic Programmming, DP) を利用すると効率良く求めることができることが知られている。以下は Python によるその実装例である。

#!/usr/bin/env pyton
import sys

def print_lcs (a, b, lcs, i, j):
    if (i == 0 or j == 0):
        return
    if (a[i-1] == b[j-1]):
        print_lcs(a, b, lcs, i - 1, j - 1)
        print a[i - 1],
    else:
        if lcs[i-1][j] >= lcs[i][j-1]:
            print_lcs(a, b, lcs, i - 1, j)
        else:
            print_lcs(a, b, lcs, i, j - 1)

a = sys.argv[1]
b = sys.argv[2]

lcs = [ [0 for j in range(len(b) + 1)] for i in range(len(a)+1) ]

for i in xrange(1, len(a) + 1):
    for j in xrange(1, len(b) + 1):
        if a[i - 1] == b[j - 1]:
            x = 1
        else:
            x = 0
        lcs[i][j] = max(lcs[i-1][j-1] + x, lcs[i-1][j], lcs[i][j-1])

print_lcs(a, b, lcs, len(a), len(b))

以下は実行例。

% python lcs.py ABCBDAB BDCBA
B C B A