Algorimul e folosit pentru a gasi aparitiile unui text pattern intr-un alt text. Se da 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).

h1. Cum se calculeaza $Z()$ ?
 
Am voi arata cum se calculeaza valorile vectorului $Z()$ Z in complexitatea $O( |S| )$. 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). Acum presuspun ca sunt la pozitia i. Vreau sa calculez Z(i). Valorile 0...i-1 sunt deja calculate.
 
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;
Acest caz se imparte, la randul lui, in alte 3 subcazuri
** **Cazul 2.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 :
!zalgorithm?A.bmp!
 
 

h1. Cum se calculeaza Z() ?
Am voi arata cum se calculeaza valorile vectorului Z() in complexitatea O( |S| ). 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). Acum presuspun ca sunt la pozitia i. Vreau sa calculez Z(i). Valorile 0...i-1 sunt deja calculate. Pentru inceput voi imparti pe 2 cazuri :