Fişierul intrare/ieşire:cmlsc.in, cmlsc.outSursăad-hoc
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

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 ≤ 1024
  • Numerele din cei doi vectori nu depasesc 256

Exemplu

cmlsc.incmlsc.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 30 de puncte. O solutie mai eficienta 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.
Sursa de 100 de puncte ce foloseste programarea dinamica se gaseste aici.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content