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).

h2. Cum se calculeaza Z() ?

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.

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 :