Cod sursa(job #2449016)

Utilizator voyagerSachelarie Bogdan voyager Data 17 august 2019 20:22:12
Problema Cel mai lung subsir comun Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.85 kb
#!/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)))