h1. Z-Algorithm

h1. Date Generale

h2. Date Generale

Determinarea tuturor apariţiilor unui model, într-un text, este o problemă frecvent întâlnită la editoarele de texte. De obicei, textul este un document în editare şi modelul căutat este un anumit cuvânt, dat de utilizator. Algoritmi eficienţi pentru această problemă pot ajuta la îmbunătăţirea performanţelor editoarelor de texte. Algoritmi de potrivire a şirurilor sunt utilizaţi, de asemenea, în căutarea de modele particulare în secvenţe ADN.
Pe lângă cunoscuţii algoritmi de potrivire a şirurilor - Rabin Karp şi KMP - există şi un al treilea algoritm numit Z-Algorithm. În continuare este prezentat acest algoritm.

h1. Introducere

h2. Introducere

Se dau două şiruri $P$ şi $T$ formate din litere mici şi mari ale alfabetului englez, şi din cifre. Se cere găsirea tuturor apariţiilor şirului $P$ ca subsecvenţă a şirului $T$. Pe lângă algoritmii Rabin-Karp şi KMP, care rezolvă această problemă în $O(|P| + |T|)$, şi Z-Algorithm rezolvă această problemă în aceeaşi complexitate.
Fie $S$ un string iar $k > 1$, o poziţie din acest string. Începând de la această poziţie vom considera toate secvenţele de forma $[k..j]$, unde $k <= j <= |S|$, astfel încât $S[k..j]$ se potriveşte cu prefixul lui $S$ de aceeaşi lungime cu secvenţa $[k..j]$. Dintre toate poziţiile pe care $j$ le poate lua o vom alege pe cea mai mare, si vom defini valoarea $jmax – k + 1$ ca fiind $Z[k]$. Dacă $S[k]$ e diferit de primul caracter, atunci un astfel de $j$ nu există iar $Z[k] = 0$. Altfel spus, $Z[k]$ e definit ca lungimea maximă astfel încât $S[k..k+Z[k]-1]$ se potriveşte cu secvenţa $S[1..Z[k]]$. (Stringul $S$ este indexat începând cu poziţia $1$).

p=. !zalgorithm?forIntroduction2.bmp!

h1. Preprocesare

h2. Preprocesare

Î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 $|B| + 1$, unde $|B| = R – k + 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!

h1. Analiza complexităţii

h2. Analiza complexităţii

După cum am menţionat anterior, algoritmul are complexitatea $O(|S|)$. Complexitatea liniara se datoreaza faptului că fiecare element este vizitat de cel mult $2$ ori, iar variabila $R$ doar creşte.

h1. Aplicaţii

h2. Aplicaţii

Cum poate fi folosit vectorul $Z[]$? $Z[k] =$ lungimea celei mai lungi secvenţe ce începe la pozitia $k$ şi în acelasi timp se află la începutul şirului. Fie stringul $Pattern$ şi stringul $Text$. Pentru a afla toate apariţiile stringului $Pattern$ în $Text$ vom crea un nou string $S = Pattern + Text$, care va reprezenta suportul pe care vom calcula vectorul $Z[]$. Dupa calcularea acestuia putem afla numărul de apariţii. Astfel, ne propunem să vedem pentru fiecare poziţie din $S$ dacă $Pattern$ apare pe poziţia curentă. O apariţie pe pozitia $k$ e valida dacă şi numai dacă $Z[k] >= |Pattern|$ şi $k > |Pattern|$.
Probleme în care poate fi aplicat algoritmul prezentat:

* "Potrivirea sirurilor":http://www.infoarena.ro/problema/strmatch
* "X":http://www.infoarena.ro/problema/x

* 'Potrivirea sirurilor':problema/strmatch
* 'X':problema/x
* 'Aparitii2':problema/aparitii2

* "Password":http://codeforces.com/contest/126/problem/B