Revizia anterioară Revizia următoare
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[ 5 ] ! = S[ i+5 ]) . Bun, acum cunoscand aceste valori pentru fiecare pozitie din S problema determinarii tutoror aparitiilor devine una usoara. Definim stringul S = P(pattern) + T(textul in care vrem sa gasim pattern-ul). Acum avand Z[ i ] calculat ne vom uita la valorile din Z[ ] de la pozitiile de unde incepe textul T(adica de la pozitia P . size( ), stringul S e indexat de la 0); O aparitie e valabila daca Z[ i ] > = n(n = lungimea pattern-ului).
Am voi arata cum se calculeaza valorile vectorului Z[ ] in complexitatea o( S . size( ) ). Fie stringul S si vectorul Z[ ]; definesc zBox ca fiind cea mai din dreapta secventa care apare la inceputul sirului. Deci pe parcursul calcularii vectorului Z[ ] voi tine 2 variabile de genul St = capatul stang unde incepe secventa; Dr = capatul drept, unde se termina( Acest zBox va fi tot timpul cea mai din dreapta secventa; 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 :
