You are viewing a single comment's thread. Return to all comments →
def lcs(a, b): n = len(a) m = len(b) #create dp ie. like an empty matrix dp = [[ [] for j in range(m+1)] for i in range(n+1)] #lcs logic for i in range(1, n+1): for j in range(1, m+1): if a[i-1] == b[j-1]: dp[i-1][j-1].append(a[i-1]) dp[i][j] = dp[i-1][j-1].copy() else: temp = max(dp[i][j-1], dp[i-1][j], key = len) dp[i][j] = temp.copy() return dp[n][m] n, m = map(int, input().split(' ')) a = list(map(int, input().split(' '))) b = list(map(int, input().split(' '))) result = lcs(a, b) for i in result: print(i, end = " ")
Seems like cookies are disabled on this browser, please enable them to open this website
The Longest Common Subsequence (LCS)
You are viewing a single comment's thread. Return to all comments →
my python3 solution