zAlgorithm
h1. Z-Algorithm
Algorimul e folosit pentru a gasi aparitiile unui text pattern intr-un alt text.
Deci avem 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).
Am voi arata cum se calculeaza valorile vectorului Z[ ] in complexitatea o( S . size( ) ). Fie stringul S si vectorul Z[ ]; definesc zBox ca fiind cea mai din dreapta secventa care apare la inceputul sirului. Deci pe parcursul calcularii vectorului Z[ ] voi tine 2 variabile de genul St = capatul stang unde incepe secventa; Dr = capatul drept, unde se termina( Acest zBox va fi tot timpul cea mai din dreapta secventa; Atentie asta nu inseamna ca e si cea mai lunga). Bun, acum sa presupunem ca sunt la pozitia i. Vreau sa calculez Z[ i ]; am calculate celelalte valori(0...i-1); Pentru inceput voi imparti pe 2 cazuri :
Cazul 1) i > Dr => nu pot face nici o observatie logica, deci voi face brutul; adica voi lua caracater cu caracater si voi compara : iau caracterul i si il compar cu caracterul 0, apoi caracterul i+1 il compar cu caracterul 1(ma opresc cand gasesc 2 caractere diferite)
Cazul 2) i <= Dr;
Pentru inceput o sa definesc :
lungAlpha = lungimea zBox-ului = Dr – St + 1;
lungBeta = lungimea secventei de la pozitia i la capatul drept al zBox-ului, adica = Dr – i + 1;
Imi propun sa mut zBox-ul la inceputul sirului (pentru ca eu stiu ca se afla acolo)
Fie aceasta noua secventa zBox2; valorea Z[i] o voi calcula pe baza unor observatii logice din zBox2; asa ca o sa am nevoie de simetricul lui i in raport cu zBox2 si de simetricul lui Dr tot in raport cu zBox2 =>
Dr2 = 0 + lungAlpha – 1;
i2 = Dr2 – lungBeta + 1;
h2. Date Generale
Acum voi imparti pe 3 cazuri :
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.
Cazul a) Z[i2] < lungBeta; adica cea mai lunga secventa ce se gaseste la inceputul sirului si incepe la pozitia i2 nu depaseste zBox-ul => Z[i] = Z[i2];
Fie stringul S :
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$).
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!
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$.
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:
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:
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 $|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!
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.
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':problema/strmatch
* 'X':problema/x
* 'Aparitii2':problema/aparitii2
* "Password":http://codeforces.com/contest/126/problem/B
