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

最長共通部分列とは列X、Yが与えられた時に共通する部分列の数である。共通文字列の順番は同じでなければいけないが、文字列が連続している必要はない。
例えば、myabcuuuとabcjjuという2つの文字列が与えられた時、最長部分列はabcuとなる。

これは典型的なDPで解くことが可能。

以下の配列DPにおいて、DPの要素DP[i][j]は、Xを左からi文字文切り出した部分文字列とYを左からj文字文切り出した部分文字列の共通部分列長である。

X = 'myabcuuu'
Y = 'abcjju'
dp = [[0 for i in range(len(X)+1)] for j in range(len(Y)+1)] #0で初期化

for i in range(len(Y)):
    for j in range(len(X)):
        if X[j] == Y[i]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

[[0, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 1, 1, 1, 1, 1, 1],
 [0, 0, 0, 1, 2, 2, 2, 2, 2],
 [0, 0, 0, 1, 2, 3, 3, 3, 3],
 [0, 0, 0, 1, 2, 3, 3, 3, 3],
 [0, 0, 0, 1, 2, 3, 3, 3, 3],
 [0, 0, 0, 1, 2, 3, 4, 4, 4]]