白駿9251号:LCS
2071 ワード
問題解決の考え方
この問題はバックパック問題と同様に,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)])
✔関連概念
Reference
この問題について(白駿9251号:LCS), 我々は、より多くの情報をここで見つけました https://velog.io/@dlehdtjq00/백준-9251번-LCSテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol