Cod sursa(job #2449014)

Utilizator voyagerSachelarie Bogdan voyager Data 17 august 2019 20:19:22
Problema Cel mai lung subsir comun Scor 50
Compilator py Status done
Runda Arhiva educationala Marime 0.85 kb
#!/usr/bin/env python3

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 in range(len(a)):
    for j in 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)))