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 langa cunoscutii algoritmi de potrivire a sirurilor : Rabin Karp si KMP exista si un al treilea algoritm numit Z-Algorithm. In continuare este prezentat acest algoritm.

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 doua siruri P si T formate din litere mici si mari ale alfabetului englez si din cifre. Se cere gasirea tuturor aparitiilor sirului P ca subsecventa a sirului T. Pe langa algoritmii Rabin-Karp si Kmp care rezolva aceasta problema in O( $|P| + |T|$ ) si Z-Algorithm rezolva aceasta problema in aceeasi complexitate.
Fie S un string iar k > 1, o pozitie din acest string. Incepand de la aceasta pozitie vom considera toate secventele de forma $[k..j]$, unde $k <= j <= |S|$, astfel incat $S[k..j]$ se potriveste cu prefixul lui S de aceeasi lungime cu secventa $[k..j]$. Dintre toate pozitiile pe care j le poate lua o vom alege pe cea mai mare, si vom defini valoarea $jmax – k + 1$ ca fiind $Z[k]$. Daca $S[k]$ e diferit de primul caracter atunci un astfel de j nu exista iar $Z[k] = 0.$ Altfel spus, $Z[k]$ e definit ca lungimea maxima astfel incat $S[k..k+Z[k]-1]$ se potriveste cu secventa $S[1..Z[k]].$( Stringul S este indexat incepand cu pozitia 1).

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

Fie $S = {aabadaabcaaba}.$
Vom defini Z-boxul pentru pozitia k ca fiind secventa ce incepe la pozitia k si se termina la pozitia $k + z[k] – 1.$ Pentru o pozitie k > 1, vom considera toate Z-boxurile ce incep la pozitia j astfel incat $2 <= j <= k$. Dintre toate aceste Z-boxuri vom selecta Z-boxul care are cel mai mare capat drept si il vom numi $R[k].$ Pe langa acest capat drept vom mai tine si capatul stang al acestui Z-box in $L[k].$ In continuare sunt prezentate $R[k]$ si $L[k]$ asociate stringului S. Sagetile indica Z-boxul fiecarei pozitii.

Fie $S = {aabadaabcaaba}$.
Vom defini Z-boxul pentru poziţia $k$ ca fiind secvenţa ce începe la poziţia $k$ şi se termină la poziţia $k + z[k] – 1$. Pentru o poziţie $k > 1$, vom considera toate Z-boxurile ce încep la poziţia $j$ astfel încât $2 <= j <= k$. Dintre toate aceste Z-boxuri vom selecta Z-boxul care are cel mai mare capăt drept şi îl vom numi $R[k]$. Pe lângă acest capăt drept vom mai ţine şi capătul stâng al acestui Z-box în $L[k]$. În continuare sunt prezentate $R[k]$ şi $L[k]$ asociate stringului $S$. Săgeţile indică Z-boxul fiecarei poziţii.

p=. !zalgorithm?forIntroduction1.bmp!
p=. !zalgorithm?forIntroduction2.bmp!

h1. Preprocesare

h2. Preprocesare

In continuare vom prezenta partea de preprocesare, adica, calcularea vectorului $Z[]$. Cand aflam valoarea $Z[k]$ vom avea nevoie doar de valorile $R[k-1]$ si $L[k-1].$ De aceea nu are sens sa tinem aceste valori in 2 vectori asa ca le vom tine in 2 variabile R si L care vor fi actualizate la fiecare pas. Algoritmul incepe sa calculeze vectorul $Z[]$ de la pozitia 2.( $Z(1)$ = lungimea stringului). Sa presupunem ca suntem la pozitia k, k>=2, iar toate celelalte k-1 valori sunt calculate. Algoritmul ia in considerare urmatoarele cazuri :

Î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.$** In acest caz algoritmul nu se poate folosi de nici o informatie obtinuta anterior. Astfel, algoritmul va efectua comparatii intre doua caractere incepand cu cel de pe pozitia k respectiv pozitia 1 pana cand va gasi o nepotrivire. Ca urmare $Z[k]$ ia valoarea lungimii secventei care se potriveste iar $L = k si 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 aceasta data ne putem folosi de informatiile obtinute pentru pozitiile anterioare. Din moment ce k<=R rezulta ca k face parte din Zbox-ul cel mai din dreapta.  Prin definitia lui L si R, $S[k]$ apartine secventei $S[L..R].$ Notam cu A aceasta secventa. A se potriveste cu prefixul de aceeasi lungime a lui S. Astfel caracterul $S[k]$ mai apare in secventa $S[1..|A|]$ la pozitia k` = k – L + 1. Secventa $S[k..R]$ apare si in secventa $[1..|A|].$ Notam cu B secventa $S[k..R].$ Secventa B este la fel cu secventa $S[k`...|A|],$ unde $|A| = R-L+1.$ Urmatoarea imagine prezinta 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 sa-l numim C. Substringul C este si el un prefix de-al lui S. Astfel $Z[k]$ va fi egal, cel putin, cu minimul dintre $Z[k`]$ si $|B|$, unde $|B| = R – k + 1.$ In continuare apar 2 cazuri :

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 2.a) Z[k`] < |B|$**. In acest caz $Z[k]$ are aceeasi valoare ca si $Z[k`].$ Din moment ce $Z[k] < |B|$ variabilele R si L raman neschimbate. Urmatoarea imagine exemplifica 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 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 :

* $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 complexitatii

h2. Analiza complexităţii

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.

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

h2. Aplicaţii

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

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 in care poate fi aplicat algoritmul prezentat:

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