Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cmlsc.in, cmlsc.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Cel mai lung subsir comun
Fie v un vector cu N elemente. Se numeste subsir de lungime K al vectorului v un nou vector v' = (vi1, vi2, ... viK), cu i1 < i2 < ... < iK. De exemplu, vectorul v = (5 7 8 9 1 6) contine ca subsir sirurile (5 8 6) sau (7 8 1), dar nu contine subsirul (1 5). Se dau doi vectori A si B cu elemente numere naturale nenule.
Cerinta
Sa se determine subsirul de lungime maxima care apare atat in A cat si in B.
Date de intrare
Fisierul de intrare cmlsc.in contine pe prima linie M si N, numarul de elemente pentru vectorul A, respectiv pentru B. A doua linie contine M numere naturale, elementele vectorului A. A treia linie contine descrierea vectorului B sub acelasi format.
Date de iesire
Fisierul de iesire cmlsc.out va contine pe prima linie MAX, lungimea maxima a unui subsir comun. A doua linie va contine MAX numere ce reprezinta un subsir comun pentru A si B. Daca exista mai multe solutii se poate afisa oricare.
Restrictii
- 1 ≤ M, N ≤ 256
Exemplu
| cmlsc.in | cmlsc.out |
|---|---|
| 5 3 1 7 3 9 8 7 5 8 | 2 7 8 |
Indicatii de rezolvare
Problema celui mai lung subsir comun pentru doua siruri A si B se poate rezolva in timp exponential prin metoda backtracking. Sursa unei astfel de abordari se gaseste aici si obtine ? puncte. Rezolvarea optima are complexitatea O(M * N), daca se utilizeaza programarea dinamica. Algoritmul din spatele unei astfel de rezolvari este foarte bine explicat atat pe wikipedia, cat si in cartea Introducere in algoritmi, Thomas Cormen, editura Agora, Cluj-Napoca, paginile 270-274.
Sursa de 100 de puncte ce foloseste programarea dinamica se gaseste aici.
