Mai intai trebuie sa te autentifici.
Cod sursa(job #2449011)
| Utilizator | Data | 17 august 2019 20:12:42 | |
|---|---|---|---|
| Problema | Cel mai lung subsir comun | Scor | 40 |
| Compilator | py | Status | done |
| Runda | Arhiva educationala | Marime | 0.84 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 j > 0 and lg[i-1][j] <= lg[i][j-1]:
j -= 1
else:
i -= 1
print(' '.join(reversed(sol)))
