Incep cu observatia ca, mai demult, ni s-a reprosat ca tinem stacheta
prea sus si ca ar fi bine sa dam si probleme mai usoare. Am facut
acest lucru; problemele 8 si 9 sunt putin mai grele decat ce se
gaseste prin manualul de clasa a X-a: un algoritm de umplere si o
problema de baza in programarea dinamica. Totusi, cei care au trimis
probleme au fost aceiasi de la toate etapele. Ca urmare, o sa ridicam
stacheta (aproape) la loc, cel putin pana la ONI.

Pentru a rezolva problema 9, sa consideram urmatorul caz simplificat:
Am doua siruri, A de lungime M si B de lungime N. Asupra sirului A am
voie sa efectuez urmatoarele operatii:

a) Stergerea unui caracter;
b) Inserarea unui caracter;
c) Modificarea unui caracter.

Se cere sa se afle numarul minim de operatii necesar pentru a
transforma sirul A in sirul B. Acest numar este cunoscut sub numele de
distanta Lowenstein intre siruri.

Pentru aflarea acestui numar vom introduce niscaiva notatii:
- Fie A[1..i] si B[1..j] sirul format din primele i caractere ale lui A,
  respectiv sirul format din primele j caractere ale lui B, cu
  conventia ca daca i=0, A[1..i] este sirul vid, si similar pentru B.
- Fie D[i,j] distanta Lowenstein de la A[1..i] la B[1..j]. Scopul
  vietii noastre, restrictionat la aceasta problema, este de a afla
  D[M,N], intrucat A[1..M] si B[1..N] reprezinta intregile siruri A si B.

Facem urmatoarele afirmatii (pe care nu le demonstram riguros, pentru ca
afirmatiile nefondate au mare trecere in Romania):

1) D[0,j]=j, D[i,0]=i. Intr-adevar, trecerea de la sirul vid la un sir
de lungime j se face prin simpla inserare a celor j caractere, iar
trecerea de la sirul de lungime i la sirul vid se face prin i operatii
de stergere.

2) Daca A[i]=B[j], atunci D[i,j]=D[i-1,j-1]. Pseudo-demonstratie:
daca ultimele caractere ale lui A[1..i] si B[1..j] coincid, atunci
facem asupra sirului A[1..i] exact operatiile pe care le faceam asupra
lui A[1..i-1] pentru a-l transforma in B[1..j-1]. Aceasta ne va
conduce tocmai la sirul B[1..j], deoarece ultimul caracter nu
presupune nici o operatie speciala.

3) Daca A[i]<>B[j], avem trei modalitati de a calcula D[i,j], si o vom
folosi pe cea care produce o valoare minima:

a) Transformam A[1..i-1] in B[1..j-1], iar caracterul A[i] il
modificam in B[j], cu alte cuvinte D[i,j]=1+D[i-1,j-1];
b) Transformam A[1..i-1] in B[1..j] si stergem caracterul suplimentar
A[i], deci D[i,j]=1+D[i-1,j];
c) Transformam A[1..i] in B[1..j-1] si adaugam caracterul necesar
B[j], deci D[i,j]=1+D[i,j-1].

Rezumand, obtinem ca:

           /  D[i-1,j-1] daca A[i]=B[j]
D[i,j]=  <
           \  1 + min(D[i-1,j-1], D[i-1,j], D[i,j-1]) daca A[i]<>B[j]

Exemplu:

           B
       b a b a n u
     0 1 2 3 4 5 6
   f 1 1 2 3 4 5 6
 A a 2 2 1 2 3 4 5
   n 3 3 2 2 3 3 4
   e 4 4 3 3 3 4 4

Generalizarea pentru V siruri este aproape evidenta. Relatiile sunt
exact aceleasi, doar ca testul A[i]=B[j] se inlocuieste cu A[i]
apartine multimii P[1,j], P[2,j], ..., P[V][j].

Completarea matricei D se face pe linie. Practic, pentru completarea
unei linii din matrice avem nevoie doar de elementele liniei
anterioare. Din acest motiv, putem opera cu doi vectori, asa incat din
D[0] deducem D[1], din D[1] deducem D[2] etc.

Nu mai detaliem acum (dar daca vreti cereti si poate vi se va da)
urmatoarea intrebare care decurge natural: bun, am aflat distanta de
la A la B (respectiv la P), dar care sunt efectiv transformarile pe
care le aplic ?

Inchei cu speranta ca a ajuns cineva sa citeasca si acest rand.