În continuare vom prezenta partea de preprocesare, adică, calcularea vectorului $Z[]$. Când aflam valoarea $Z[k]$ vom avea nevoie doar de valorile $R[k-1]$ şi $L[k-1]$. De aceea nu are sens să ţinem aceste valori în doi vectori, aşa că le vom ţine în două variabile $R$ şi $L$ care vor fi actualizate la fiecare pas. Algoritmul începe să calculeze vectorul $Z[]$ începând cu poziţia $2$, $Z(1)$ fiind egal cu lungimea stringului. Să presupunem că ne aflăm la poziţia $k$, $k >= 2$, iar toate celelalte $k-1$ valori sunt calculate. Algoritmul ia în considerare următoarele cazuri:

**$Cazul 1: k > R.$** În acest caz algoritmul nu se poate folosi de nici o informaţie obţinută anterior. Astfel, algoritmul va efectua comparaţii între două caractere începând cu cel de pe poziţia $k$, respectiv poziţia $1$, până când va găsi o nepotrivire. Ca urmare, $Z[k]$ ia valoarea lungimii secvenţei care se potriveşte iar $L = k$ şi $R = k + Z[k] – 1$.

* $Cazul 1: k > R.$ În acest caz algoritmul nu se poate folosi de nici o informaţie obţinută anterior. Astfel, algoritmul va efectua comparaţii între două caractere începând cu cel de pe poziţia $k$, respectiv poziţia $1$, până când va găsi o nepotrivire. Ca urmare, $Z[k]$ ia valoarea lungimii secvenţei care se potriveşte iar $L = k$ şi $R = k + Z[k] – 1$.

p=. !zalgorithm?case1.bmp!

**$Cazul 2: k <= R.$** De această dată ne putem folosi de informaţiile obţinute pentru poziţiile anterioare. Din moment ce $k <= R$ rezultă că poziţia $k$ face parte din Zbox-ul cel mai din dreapta. Prin definiţia lui $L$ şi $R$, $S[k]$ aparţine secventei $S[L..R]$. Notăm cu $A$ această secvenţă. $A$ se potriveşte cu prefixul de aceeaşi lungime al lui $S$. Astfel, caracterul $S[k]$ mai apare în secvenţa $S[1..|A|]$ la pozitia $k' = k – L + 1$. Secvenţa $S[k..R]$ apare şi în secvenţa $[1..|A|]$. Notăm cu $B$ secvenţa $S[k..R]$. Secvenţa $B$ coincide cu secvenţa $S[k'...|A|]$, unde $|A| = R - L + 1$. Următoarea imagine prezintă aceste lucruri:

* $Cazul 2: k <= R.$ De această dată ne putem folosi de informaţiile obţinute pentru poziţiile anterioare. Din moment ce $k <= R$ rezultă că poziţia $k$ face parte din Zbox-ul cel mai din dreapta. Prin definiţia lui $L$ şi $R$, $S[k]$ aparţine secventei $S[L..R]$. Notăm cu $A$ această secvenţă. $A$ se potriveşte cu prefixul de aceeaşi lungime al lui $S$. Astfel, caracterul $S[k]$ mai apare în secvenţa $S[1..|A|]$ la pozitia $k' = k – L + 1$. Secvenţa $S[k..R]$ apare şi în secvenţa $[1..|A|]$. Notăm cu $B$ secvenţa $S[k..R]$. Secvenţa $B$ coincide cu secvenţa $S[k'...|A|]$, unde $|A| = R - L + 1$. Următoarea imagine prezintă aceste lucruri:

p=. !zalgorithm?case2.bmp!
Cand $k'$ a fost calculat, s-a format un Z-Box de lungime $Z[k']$. O să-l numim $C$. Substringul $C$ este şi el un prefix de-al lui $S$. Astfel, $Z[k]$ va fi egal, cel puţin, cu minimul dintre $Z[k']$ şi $|B|$, unde $|B| = R – k + 1$. În continuare apar două cazuri:

**$Cazul 2a: Z[k'] < |B|$**. În acest caz $Z[k]$ are aceeaşi valoare ca şi $Z[k']$. Din moment ce $Z[k] < |B|$, variabilele $R$ şi $L$ rămân neschimbate. Următoarea imagine exemplifică acest caz:

* $Cazul 2a: Z[k'] < |B|.$ În acest caz $Z[k]$ are aceeaşi valoare ca şi $Z[k']$. Din moment ce $Z[k] < |B|$, variabilele $R$ şi $L$ rămân neschimbate. Următoarea imagine exemplifică acest caz:

p=. !zalgorithm?case2_a.bmp!

**$Cazul 2b: Z[k'] >= |B|$**. În acest caz $Z[k]$ va fi cel puţin egal cu $|B|$. Dar acesta mai poate fi extins. Asta l-ar face pe $Z[k]$ mai mare decât $Z[k']$. Astfel, algoritmul încearca să extindă Z-Boxul lui $k$. Începe să facă comparaţii de la poziţiile $R + 1$ şi $|A| + 1$, unde $|A| = R – L + 1$, până când găseşte o nepotrivire. Notăm cu $q$ poziţia primei nepotriviri. Atunci, $Z[k] = q – 1 – (k – 1) = q – k$, $R = q - 1$ şi $L = k$. Următoarea imagine exemplifică acest caz:

* $Cazul 2b: Z[k'] >= |B|$. În acest caz $Z[k]$ va fi cel puţin egal cu $|B|$. Dar acesta mai poate fi extins. Asta l-ar face pe $Z[k]$ mai mare decât $Z[k']$. Astfel, algoritmul încearca să extindă Z-Boxul lui $k$. Începe să facă comparaţii de la poziţiile $R + 1$ şi $|A| + 1$, unde $|A| = R – L + 1$, până când găseşte o nepotrivire. Notăm cu $q$ poziţia primei nepotriviri. Atunci, $Z[k] = q – 1 – (k – 1) = q – k$, $R = q - 1$ şi $L = k$. Următoarea imagine exemplifică acest caz:

p=. !zalgorithm?case2_b.bmp!