最長共通部分列(動的計画法③)

最長共通部分列

部分列 は系列のいくつかの要素を取り出してできた系列のことです。

二つの系列の共通の部分列を 共通部分列 と言います。

共通部分列のうちもっとも長いものを 最長共通部分列 と言います。

最長共通部分列 を求める問題を 動的計画法 を使って解いていきます。

問題

2つの文字列があります。

これら2つの共通部分列の長さの最大値を求めて下さい。

解法・ソースコード

メモ化テーブル を次のように定義します。

memo[i][j] は、【1つめの文字列のi文字まで】と【2つめの文字列のj文字まで】の

最長共通部分列の長さ

この定義を踏まえて、漸化式 を作成し 動的計画法(メモ化テーブル) を実装すると次のようになります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#---------- 入力例 ----------
a = 'ABCBDAB'
b = 'BDCABA'
#----------------------------
# メモ化テーブル
memo = {}

for i, a1 in enumerate(a):
for j, b1 in enumerate(b):
if a1 == b1: # 文字が一致した場合
# 最長共通部分列の長さを1つ増やす
memo[i + 1, j + 1] = memo.get((i, j), 0) + 1
else: # 文字が一致しない場合
# これまでの最長共通部分列で長いほうを選択
memo[i + 1, j + 1] = max(memo.get((i, j + 1), 0), memo.get((i + 1, j), 0))

print('解:', memo[(len(a), len(b))])

[実行結果]

解: 4

解は 4 となりました。

2つの文字列を確認すると 最長共通部分列B, C, B, A となっていて解が正しいことが分かります。