python練習 最長部分列（LCS）
最長部分列（LCS）
最長部分列（LCS）の練習です。しっかり体に叩き込みましょう。
関連タイピング
-
プレイ回数206 英語長文90秒 -
プレイ回数38 英語60秒 -
プレイ回数42 英語長文312打 -
プレイ回数63 英語長文426打
-
プレイ回数119 英語長文900打 -
プレイ回数31 英語90秒 -
プレイ回数62 英語900打
-
プレイ回数36 英語長文931打
問題文
ふりがな非表示
ふりがな表示
(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)