h1. Despre ce e vorba ?

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

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()$ ?