python練習　最長部分列（LCS）

背景
投稿者投稿者kurimats  いいね0  お気に入り登録
プレイ回数62  難易度(2.9) 362打 英語
最長部分列（LCS）
最長部分列（LCS）の練習です。しっかり体に叩き込みましょう。

関連タイピング

関連タイピング一覧

問題文

ふりがな非表示 ふりがな表示

(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)

問題文を全て表示 一部のみ表示 誤字・脱字等の報告