h2. 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). Valorilesunt deja calculate. Pentru inceput voi imparti pe 2 cazuri.