Advertisement
KateWilson

Наибольшая общая подпоследовательность

Sep 2nd, 2019
251
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.80 KB | None | 0 0
  1. #Выводит только размер подпоследовательности
  2. a = input().split()
  3. b = input().split()
  4. n = len(a)
  5. m = len(b)
  6. F = [[0] * (m + 1) for i in range(n + 1)]
  7. if a or b == 0:
  8.     print(F[n][m])
  9. else:
  10.     for i in range(1,n+1):
  11.         for j in range(1,m+1):
  12.             if a[i-1] == b[j-1]:
  13.                 F[i][j] = F[i-1][j-1] + 1
  14.             elif a[i-1] != b[j-1]:
  15.                 F[i][j] = max(F[i-1][j], F[i][j-1])
  16.     print(F[n][m])
  17. #Вывод самой подпоследовательности
  18. answer = []
  19. i = n
  20. j = m
  21. while i > 0  and j > 0:
  22.     if a[i-1] == b[j-1]:
  23.         answer.append(a[i-1])
  24.         i-=1
  25.         j-=1
  26.     elif F[i-1][j] == F[i][j]:
  27.         i-=1
  28.     else:
  29.         j-=1
  30. answer = answer[ : :-1]
  31. print(' '.join(map(str,answer)))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement