infoarena informatica de performanta

zAlgorithm

Algorimul e folosit pentru a gasi aparitiile unui text pattern intr-un alt text.
Deci avem textul P si textul T; vrem sa gasim toate aparitiile lui P in T.
Algoritmul vine cu o idee in felul urmator: fie stringul S si fie vectorul Z[i] = lungimea celei mai lungi secvente ce incepe la pozitia i si se gaseste la inceputul stringului S; adica, de exemplu daca Z[i] = 5 => secventa 0...4 e la fel cu i,..,i+5-1(fiind cea mai mare => S⁵ !!Atentie asta nu inseamna ca e si cea mai lunga). Bun, acum sa presupunem ca sunt la pozitia i. Vreau sa calculez Z[i]; am calculate celelalte valori(0...i-1); Pentru inceput voi imparti pe 2 cazuri :
Cazul 1) i > Dr => nu pot face nici o observatie logica, deci voi face brutul; adica voi lua caracater cu caracater si voi compara : iau caracterul i si il compar cu caracterul 0, apoi caracterul i+1 il compar cu caracterul 1(ma opresc cand gasesc 2 caractere diferite)

Cazul 2) i <= Dr;
Pentru inceput o sa definesc :
lungAlpha = lungimea zBox-ului = Dr – St + 1;
lungBeta = lungimea secventei de la pozitia i la capatul drept al zBox-ului, adica = Dr – i + 1;
Imi propun sa mut zBox-ul la inceputul sirului (pentru ca eu stiu ca se afla acolo)
Fie aceasta noua secventa zBox2; valorea Z[i] o voi calcula pe baza unor observatii logice din zBox2; asa ca o sa am nevoie de simetricul lui i in raport cu zBox2 si de simetricul lui Dr tot in raport cu zBox2 =>
Dr2 = 0 + lungAlpha – 1;
i2 = Dr2 – lungBeta + 1;

Acum voi imparti pe 3 cazuri :

Cazul a) Z[i2] < lungBeta; adica cea mai lunga secventa ce se gaseste la inceputul sirului si incepe la pozitia i2 nu depaseste zBox-ul => Z[i] = Z[i2];
Fie stringul S :

St2 I2 Dr2 St I Dr
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14 
(nu prea are relevanta sa contina si caracatere)
Fie St = 7,  Dr = 12 si i = 10; acum voi muta zBox-ul la inceput =>
lungAlpha = 6; lungBeta = 3;
St2 = 0; Dr2 = 5; i2 = 3;
Eu am calculat Z[i2] si stiu ca e < lungBeta => Z[i] = Z[i2], e adevarat pentru ca Zbox e la fel cu Zbox2;

Cazul b) Z[i2] > lungBeta => Z[i] = lungBeta;
St2 I2 Dr2 St I Dr
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14 
Acum voi face o modificare, i-ul va fi 11 nu 10 (pentru a fi mai clar pe exemplu)=>
St = 7, Dr = 12, I = 11; => St2 = 0; Dr2 = 5; i2 = 4;
Eu stiu acum ca Z[i2] > lungBeta; deci secventa 4..5 e la fel cu 0..1 si e la fel cu 11..12
Avand in vedere ca Z[i2] > lungBeta => si caracterul 6 e la fel cu caracterul 2;
Doar ca se poate face o observatie din care rezulta ca Z[i] = lungBeta; Pentru a demonstra ca e asa voi presupune ca nu e asa => Z[i] > lungBeta => S¹³ = S⁶ (care e = S²) daca acest lucru ar fi adevarat atunci Zbox-ul nu ar fi secventa 7..12 ci ar fi secventa 7..13 => Presupunerea initiala e falsa => Z[i] = lungBeta

Cazul c) Z[i2] = lungBeta => Z[i] = lungBeta + compara();
St2 I2 Dr2 St I Dr
0  1  2  3  4  5  6  7  8  9  10  11  12  13  14 
Acum Z[i2] = lungBeta, de aici rezulta urmatoarele observatii :
S² = S¹³ Doar ca asta nu inseamna ca S² != S¹³(s-ar putea sa fie la fel; trebuie verificat) => Z[i] = lungBeta + compara(lungBeta, Dr + 1);
Compara( i, j) = e o functie care primeste 2 indici si incepe sa compare caracaterele incepand cu cei 2 indici pana cand gaseste 2 caractere diferite

Analiza complexitatii:
In primul rand complexitatea este liniara O(n + m); n = lungimea stringului P
M = lungimea stringului T; Complexitatea este liniara deoarece fiecare element este vizitat de cel mult 2 ori iar zBox-ul e tot timpul cea mai din dreapta secventa;

Mai jos am sa propun o modalitate de implementare a acestui algoritm :
O sa urmeze …