cmlsc

Cmlsc

h2. Restrictii

* $1 ≤ M, N ≤ 256$

* $1 ≤ M, N ≤ 1024$

* Numerele din cei doi vectori nu depasesc $256$
h2. Exemplu

7 8
|

h3. Indicatii de rezolvare

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.

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. 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':http://en.wikipedia.org/wiki/Longest_common_substring_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/143064?action=view-source.

== include(page="template/taskfooter" task_id="cmlsc") ==

2760