Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from collections import deque
- first = [int(x) for x in input().split()]
- second = [int(x) for x in input().split()]
- result = deque()
- rows = len(first) + 1
- cols = len(second) + 1
- dp = [[0] * cols for _ in range(rows)]
- for row in range(1, rows):
- for col in range(1, cols):
- if first[row-1] == second[col -1]:
- dp[row][col] = dp[row-1][col-1] + 1
- else:
- dp[row][col] = max(dp[row-1][col], dp[row][col-1])
- best_len = dp[rows-1][cols-1]
- row = rows - 1
- col = cols - 1
- while row > 0 and col > 0:
- if first[row-1] == second[col -1]:
- result.appendleft(first[row - 1])
- row -= 1
- col -= 1
- elif dp[row-1][col] > dp[row][col-1]:
- row -= 1
- else:
- col -= 1
- print(*result)
- print(best_len)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement