python練習 最長部分列（LCS）
関連タイピング
-
プレイ回数13英語長文931打 -
プレイ回数30英語長文312打 -
プレイ回数37英語長文900打 -
プレイ回数86英語長文900打
-
プレイ回数105英語長文324打 -
プレイ回数114英語長文90秒 -
プレイ回数36英語60秒
-
atcoder py kurimatsの型 難
プレイ回数29英語長文493打
問題文
(def dp(S,T):)
def dp(S,T):
(m,n=len(S),len(T))
m,n=len(S),len(T)
(dp=[[0]*(n+1) for _ in range(m+1)])
dp=[[0]*(n+1) for _ in range(m+1)]
(for i in range(1,m+1):)
for i in range(1,m+1):
(for j in range(1,n+1):)
for j in range(1,n+1):
(if s[i-1]==t[j-1]:)
if s[i-1]==t[j-1]:
(dp[i][j]=dp[i-1][j-1]+1)
dp[i][j]=dp[i-1][j-1]+1
(else:)
else:
(dp[i][j]=max(dp[i-1][j],dp[i][j-1]))
dp[i][j]=max(dp[i-1][j],dp[i][j-1])
(lcs="")
lcs=""
(i,j=m,n)
i,j=m,n
(while i>0 and j>0:)
while i>0 and j>0:
(if s[i-1]==t[j-1]:)
if s[i-1]==t[j-1]:
(lcs=s[i-1]+lcs)
lcs=s[i-1]+lcs
(i-=1)
i-=1
(j-=1)
j-=1
(elif dp[i-1][j] > dp[i][j-1]:)
elif dp[i-1][j] > dp[i][j-1]:
(else:)
else:
(j-=1)
j-=1
(return dp[m][n],lcs)
return dp[m][n],lcs
(S=input())
S=input()
(T=input())
T=input()
(length,lcs=dp(S,T))
length,lcs=dp(S,T)
(print(lcs))
print(lcs)