Advertisement
viligen

longest_common_subs_with_values_DP

Aug 11th, 2022
684
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.79 KB | None | 0 0
  1. from collections import deque
  2.  
  3. first = [int(x) for x in input().split()]
  4. second = [int(x) for x in input().split()]
  5.  
  6. result = deque()
  7.  
  8. rows = len(first) + 1
  9. cols = len(second) + 1
  10.  
  11. dp = [[0] * cols for _ in range(rows)]
  12.  
  13. for row in range(1, rows):
  14.     for col in range(1, cols):
  15.         if first[row-1] == second[col -1]:
  16.             dp[row][col] = dp[row-1][col-1] + 1
  17.  
  18.         else:
  19.             dp[row][col] = max(dp[row-1][col], dp[row][col-1])
  20.  
  21.  
  22. best_len = dp[rows-1][cols-1]
  23.  
  24. row = rows - 1
  25. col = cols - 1
  26.  
  27. while row > 0 and col > 0:
  28.     if first[row-1] == second[col -1]:
  29.         result.appendleft(first[row - 1])
  30.         row -= 1
  31.         col -= 1
  32.  
  33.     elif dp[row-1][col] > dp[row][col-1]:
  34.         row -= 1
  35.     else:
  36.         col -= 1
  37.  
  38.  
  39. print(*result)
  40.  
  41. print(best_len)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement