[規格-9251]LCS

に答える

写真の出所:https://myjamong.tistory.com/317
ACAYKPとCAPCAKを例にとると、前の文のサブシーケンスがaで、後の文のサブシーケンスがbであれば、
a:A
b:CA
2つの文字列で作成可能なLCSの長さ:1
a:A
b:CA
2つの文字列で作成可能なLCSの長さ:1
...以上のように、bが1つ増えるごとにLCSの長さを求め、bが増加するとaが1つ増え、上記のようにLCSの長さを求める.
a:AC
b:C
2つの文字列で作成可能なLCSの長さ:1
a:AC
b:CA
2つの文字列で作成可能なLCSの長さ:1
aとbに同じ文字が追加された場合、aとbに文字が追加される前に、LCSの長さに+1を加えた値が追加された文字のLCSの長さに等しい.
dp[i][j]=dp[i-1][j-1]+1
aとbに追加された文字が異なる場合、既存の所与の文字列の最大長をLCS長とすることができる.
dp[i][j]=max(dp[i-1][j],dp[i][j-])

コード#コード#

import sys
input = sys.stdin.readline

s1=input().strip()
s2=input().strip()

dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]
for i in range(1,len(s1)+1):
    for j in range(1,len(s2)+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i-1][j],dp[i][j-1])

print(dp[-1][-1])

実行時間:712ミリ秒