== include(page="template/taskheader" task_id="cmlsc") ==
Poveste si cerinta...
Fie $v$ un vector cu $N$ elemente. Se numeste subsir de lungime $K$ al vectorului $v$ un nou vector {$v'$} = {$(v{~i1~}, v{~i2~}, ... v{~iK~})$}, cu {$i{~1~}$} < {$i{~2~}$} < ... < {$i{~K~}$}. 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.
h2. Cerinta
Sa se determine subsirul de lungime maxima care apare atat in $A$ cat si in {$B$}.
h2. Date de intrare
Fisierul de intrare $cmlsc.in$ ...
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.
h2. Date de iesire
In fisierul de iesire $cmlsc.out$ ...
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.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ M, N ≤ 1024$
* Numerele din cei doi vectori nu depasesc $256$
h2. Exemplu
table(example). |_. cmlsc.in |_. cmlsc.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|5 3
1 7 3 9 8
7 5 8
|2
7 8
|
h3. Explicatie
h2. Indicatii de rezolvare
Problema celui mai lung subsir comun pentru doua siruri $A$ si $B$ se poate rezolva in timp exponential prin metoda 'backtracking':http://en.wikipedia.org/wiki/Backtracking. Sursa unei astfel de abordari se gaseste 'aici':job_detail/143062?action=view-source 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':http://en.wikipedia.org/wiki/Longest_common_subsequence_problem, 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':job_detail/143144?action=view-source.
...
== include(page="template/taskfooter" task_id="cmlsc") ==
