白駿9251号:LCS

問題解決の考え方

ダイナミックプログラミング

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

✔アルゴリズムの説明
この問題はバックパック問題と同様に,2次元配列で解くDP問題である.復習しましょう.

(len(String A)+1)X(len(String B)+1)サイズを宣言する2 D配列で、デフォルト値はすべて0になります.

2つのStringを構成する各要素を前の行から1つずつ比較して、それらの値が一致するかどうかを判断します.

値が一致する場合(図中は薄荷色)、対角線方向左上隅の値に1を加えて現在の値を入れます.これは、これまでの最大共通部分数列に1を加算することを意味します.
LCS [ i ][ j ] = LCS [ i - 1 ][ j - 1 ] + 1

値が一致しない場合(図中は青)、前のプロシージャの最長値を現在の値に入れます.部分数列は連続した値ではないため、前のプロシージャの最大共通部分数列は維持されます.この場合、前のプロシージャは、テーブル内の左方向の値と上方向の値を意味します.
LCS[ i ][ j ] = max ( LCS [ i ][ j - 1 ], LCS[ i - 1 ][ j ] )

2つのStringのすべての要素を比較すると、テーブルの右下隅(最後の値)に最も値が含まれるため、この値が正しい値になります.

詳細な説明と直感的な画像については、次のリンクを参照してください.
https://velog.io/@emplam 27/アルゴリズム-図示-LCS-アルゴリズム-Longest-Common-Substringおよび-Langest-Common-Subsequence

✔実現コード

import sys

stringA = sys.stdin.readline().strip()
stringB = sys.stdin.readline().strip()
LCS = [[0]*(len(stringA)+1) for _ in range(len(stringB)+1)]

for i in range(len(stringB)):
    for j in range(len(stringA)):
        if stringB[i] == stringA[j]:
            LCS[i+1][j+1] = LCS[i][j] + 1
        else:
            LCS[i+1][j+1] = max(LCS[i+1][j], LCS[i][j+1])

print(LCS[len(stringB)][len(stringA)])

の2次元配列の大きさを1で拡大するので,上の点化式とは若干異なるかもしれないが,アルゴリズムを理解すればコードを容易に記述できる.

✔関連概念

動的プログラミングにおけるLCS問題