**$Cazul 2.b) Z[k`] >= |B|$** In acest caz $Z[k]$ va fi cel putin egal cu $|B|.$ Dar acesta mai poate fi extins. Asta l-ar face pe $Z[k]$ mai mare ca si $Z[k`].$ Astfel algoritmul incearca sa extinda Z-Boxul lui k. Incepe sa faca comparatii de la  pozitiile $R+1$ si $|A| + 1$, unde $|A| = R – L + 1$, pana cand gaseste o nepotrivire. Notam cu q pozitia primei nepotriviri. Atunci, $Z[k] = q – 1 – (k – 1) = q – k,$ $R = q-1$ si $L = k$. Urmatoarea imagine exemplifica acest caz :
p=. !zalgorithm?case2_b.bmp!

 
h1. Analiza complexitatii
 
Dupa cum am am mentionat si mai sus, algoritmul are complexitatea $O(|S|).$ Complexitatea liniara se datoreaza faptului ca fiecare element este vizitat maxim de $2$ ori iar variabila R doar creste.
 
h1. Aplicatii
 
Cum poate fi folosit vectorul $Z[]$ ? $Z[k] =$ lungimea celei mai lungi secvente ce incepe la pozitia k si in acelasi timp sa afla la inceputul sirului. Fie stringul Pattern si stringul Text. Pentru a afla toate aparitiile stringului Pattern in Text vom crea un nou string $S = P + T$, care va reprezenta suportul pe care vom calcula vectorul $Z[]$. Dupa calcularea acestuia putem afla numarul de aparitii. Astfel ne propunem sa vedem pentru fiecare pozitie din $S$ daca Pattern apare pe pozitia curenta. O aparitie pe pozitia k e valida daca si numai daca $Z[k] >= |P|$ si $k > |P|$.
 
Probleme in care poate fi aplicat algoritmul prezentat:
 
* "Potrivirea sirurilor":http://www.infoarena.ro/problema/strmatch
* "X":http://www.infoarena.ro/problema/x
* "Password":http://codeforces.com/contest/126/problem/B
 
h1. Bibliografie
 
* "String matching : The linear algorithm":http://www.eui.upm.es/~fmartin/webpgomez/Docencia/Pattern-Recognition/PR-Notes-Chapter-4.pdf