[C++, programare dinamică] Problema celui mai lung subșir comun

Fragment din cartea Algoritmica C++ de Vlad Sebastian Ionescu, Eugen Laslo.

Se dau două șiruri de caractere A și B, formate din litere mici ale alfabetului englez. Se cere găsirea unui șir de caractere C de lungime maximă care este subșir atât a lui A cât și a lui B.

Șirurile A și B se citesc din fișierul sircom.in, fiecare pe câte o linie. In fișierul sircom.out se va afișa pe prima linie lungimea celui mai lung subșir comun, iar pe a doua linie șirul găsit.

Rezolvare

Pentru a rezolva problema vom încerca să găsim o formulă de recurență pentru calculul lungimii celui mai lung subșir comun. Fie L[i][j] = lungimea celui mai lung subșir comun al subsecvențelor A[1, i] și B[1, j], pentru 1 ≤ i ≤ lungime(A) și 1 ≤ j ≤ lungime(B). Să presupunem că avem calculate toate valorile matricii L care preced elementul (p + 1, q + 1) (sunt fie pe aceeași linie și pe o coloană precedentă, fie pe o linie precedentă). Se disting două cazuri:

1. Dacă A[p + 1] == B[q + 1], atunci putem adăuga caracterul A[p + 1] celui mai lung subșir comun al secvențelor A[1, p] și B[1, q], obținând, pentru secvențele A[1, p + 1] și B[1, q + 1] un subșir comun de lungime maximă care este mai lung cu un caracter. Așadar, L[p + 1][q + 1] = L[p][q] + 1.
2. Dacă A[p + 1] != B[q + 1], atunci nu putem extinde niciun subșir de lungime maximă calculat anterior și va trebui să salvăm în L[p + 1][q + 1] lungimea celui mai lung subșir de lungime maximă calculat până acuma. Această valoare este dată de maximul dintre L[p][q + 1] și L[p + 1][q].

Timpul de execuție al acestei metode este O(N·M), unde N este lungimea primului șir, iar M este lungimea celui de-al doilea șir. Memoria folosită de algoritm este tot O(N·M), deoarece matricea L are N linii și M coloane. Putem reduce memoria folosită la O(N + M), dar sacrificăm astfel posibilitatea reconstituirii soluției. Vom descrie însă și această metodă.

Pentru a reconstitui soluția vom proceda similar cu metoda de reconstituire a unui drum a cărui lungime minimă a fost calculată cu algoritmul lui Lee. Vom folosi o functie recursivă reconst(x, y) care va afișa un subșir comun de lungime maximă. In primul rând, condiția de ieșire din recursivitate va fi dacă x < 1 sau y < 1. Dacă nu, verificăm dacă A[x] == B[y], iar dacă da, apelăm recursiv reconst(x - 1, y - 1) și afișăm A[x]. Dacă A[x] != B[y] atunci apelăm recursiv fie reconst(x - 1, y), în cazul în care L[x - 1][y] > L[x][y - 1], fie reconst(x, y - 1) altfel.


Pentru a simplifica implementarea am folosit tipul de date string pentru reținerea șirurilor de caractere. Indicii șirurilor de caractere încep de la 0, așa că trebuie să fim atenți la cum comparăm caracterele individuale, deoarece indicii matricei L încep de la 1. Singura inițializare care trebuie făcută este completarea liniei și coloanei 0 a matricei L cu valoarea 0, pentru a evita cazurile particulare ale recurenței descrise.


Prezentăm în continuare implementarea algoritmului de rezolvare.

Pentru a reduce memoria folosită la O(N + M) trebuie observat că pentru calculul unei valori L[i][j] nu avem nevoie decât de valori de pe linia curentă (L[i][j - 1]) și de pe linia precedentă (L[i - 1][j] și L[i - 1][j - 1]). Așadar, este de ajuns să folosim doar doi vectori de lungime egală cu lungimea șirului B. Unul dintre vectori, L1 va reprezenta linia precedentă liniei curente, iar celălalt vector, L2, va reprezenta chiar linia curentă. Noua formă a formulei de recurență este:

După fiecare calculare completă a lui L2, înainte de începerea unei noi iterații vectorul L2 va trebui copiat în L1, pentru ca valorile calculate la pasul curent să poată fi folosite la pasul următor. La sfârșitul algoritmului, cei doi vectori vor avea același conținut, deci răspunsul problemei va fi dat fie de L1[lungime(B)] fie de L2[lungime(B)].

Prezentăm doar modificările relevante:

Această implementare este preferabilă dacă memoria disponibilă este limitată și dacă nu se cere reconstituirea unei soluții, acest lucru fiind imposibil deoarece algoritmul păstrează doar valorile finale ale recurenței, nu și pe cele inițiale.


Exerciții:

a) Afișați întreaga matrice L pentru a înțelege mai bine formula de recurență.

b) Afișați toate subșirurile comune de lungime maximă.

c) In implementarea de mai sus am transmis parametrii A și B prin referință. Unde era indicat să se folosească transmitere prin referință constantă?

d) Scrieți o implementare care folosește vectori clasici de caractere în loc de tipul string.

e) Scrieți un program care afișează acel subșir comun de lungime maximă care este primul din punct de vedere alfabetic.

f) Se poate evita copierea vectorului L2? Dacă da, cum?