質問リンク

LCS

問題の説明

LCSは、与えられた数列Aと数列Bの場合、2つの数列の共通部分数列の中で最も長いものを表す.
例えば、2列のACAYKPとCAPCAKについて、LCSはACAKとなり、以下のようになる.
2つの数列を与えた場合、LCSの長さは?

問題を解く

昨日解答した距離の編集問と同じように回答すればよい.

ステータスの定義
L[i]:str[:i]:str[:i]およびstr 2[:j]のLCS長L[i]:str[:i]およびstr 2[:j]のLCS長L[i]:str[:i]およびstr 2[:j]のLCS長L[i][j]={L[iέ1][jέ+1,if str1[i−1]==str2[j−1]max(dp[i][j−1],dp[i−1][j],dp[i−1][j−1]),else L[i][j]=\begin{cases} L[i-1][j-1] + 1, &\text{if } str1[i-1] == str2[j-1]\\max(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]), &\text{else }\end{cases}L[i][j]={L[i−1][j−1]+1,max(dp[i][j−1],dp[i−1][j],dp[i−1][j−1]),​if str1[i−1]==str2[j−1]else その他の場合の点火式は、下図のように分かりやすい.しかし今から見れば必ずしもdp[i-1][j-1]の比較をしなければならないとは限らない.

コード

import sys

input = sys.stdin.readline

str1 = input().strip()
str2 = input().strip()
n, m = len(str1), len(str2)

dp = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if str1[i-1] == str2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1], dp[i][j-1])

print(dp[n][m])

に感銘を与える

文字列のdpを見て、すぐにその方法を思い出すのは容易ではないようで、いくつか解いて、dpが征服する日まで~