Pagini recente » Cod sursa (job #2636679) | Cod sursa (job #2137794) | Cod sursa (job #3203518) | Cod sursa (job #1674790) | Cod sursa (job #2449016)
#!/usr/bin/env python3
from itertools import product
import sys
sys.stdout = open('cmlsc.out', 'w')
a, b = [], []
with open('cmlsc.in', 'r') as fin:
fin.readline()
a = list(map(int, fin.readline().split()))
b = list(map(int, fin.readline().split()))
lg = [[0] * len(b) for _ in range(len(a))]
for i, j in product(range(len(a)), range(len(b))):
if a[i] == b[j]:
lg[i][j] = 1 + (0 if i * j == 0 else lg[i-1][j-1])
else:
if i > 0:
lg[i][j] = lg[i-1][j]
if j > 0 and lg[i][j-1] > lg[i][j]:
lg[i][j] = lg[i][j-1]
sol = []
i, j = len(a) - 1, len(b) - 1
print(lg[i][j])
while i >= 0 and j >= 0:
if a[i] == b[j]:
sol.append(str(a[i]))
i -= 1
j -= 1
elif i == 0 or j > 0 and lg[i-1][j] <= lg[i][j-1]:
j -= 1
else:
i -= 1
print(' '.join(reversed(sol)))