Cel mai lung subșir comun
Cum își dă seama un program ce s-a schimbat între două versiuni ale unui fișier? Sau cât de asemănătoare sunt două secvențe ADN? În spate stă cel mai lung subșir comun (LCS): cea mai lungă secvență de caractere care apare, în aceeași ordine, în ambele texte. Este problema-tip pentru DP pe două texte.
Problema
Primești două texte a și b. Un subșir comun păstrează ordinea caracterelor, dar poate sări peste unele, în fiecare text. Cauți lungimea maximă și un subșir care o atinge.
Scrie funcția lcs(a, b) care returnează un tuplu (lungime, subsir): lungimea celui mai lung subșir comun și unul dintre aceste subșiruri, refăcut din tabelul DP. La egalitate, în refacere mergi în sus (i -= 1). Testele sunt deja scrise.
- Construiește tabelul (n + 1) × (m + 1) cu zerouri.
- Completează-l: diagonală + 1 la caractere egale, altfel maximul dintre sus și stânga.
- Refă subșirul pornind din colțul dreapta-jos și returnează (dp[n][m], subsir).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Programare dinamică și interviuri simulate.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan