Mnogi problemi nad niskama mogu se efikasno rešiti korišćenjem \(z\)-niza (engl. \(z\)-array, \(z\)-function); na primer, ispitivanje da li se jedna niska javlja unutar druge, određivanje perioda niske (u smislu određivanja najkraće niske takve da se polazna niska može predstaviti nadovezivanjem te niske određen broj puta), itd. \(z\)-niz niske \(s\) dužine \(n\) je niz dužine \(n\) koji na poziciji \(k=0,1,\ldots, n-1\) sadrži dužinu \(z_k\) najduže podniske (tj. najdužeg segmenta) niske \(s\), koja počinje na poziciji \(k\) i prefiks je niske \(s\). Dakle, \(s[0..z_k-1]\) se poklapa sa \(s[k..k+z_k-1]\), a karakteri \(s[z_k]\) i \(s[k+z_k]\) su različiti ili je pak niska \(s\) dužine \(k+z_k\).
Primer 6.5.1. Za nisku alfalfa je \(z_3=4\), jer podniska alfa koja počinje na poziciji \(3\) i završava se na kraju niske ima dužinu \(4\) i poklapa sa prefiksom niske dužine \(4\).
Primer 6.5.2. Za nisku photophosphorescent važi \(z_5=z_9=3\), jer i na poziciji \(5\) i na poziciji \(9\) počinje podniska pho koja ima dužinu \(3\), poklapa se prefiksom niske i ne može da se produži tako da se i dalje poklapa sa odgovarajućim prefiksom.
Podnisku koja počinje na poziciji \(k\) i preklapa se sa nekim prefiksom dužine \(z_k\) nazivamo i \(z\)-kutija (engl. \(z\)-box). Primer \(z\)-kutije ilustrovan je na slici 1. Ako je vrednost \(z_k=0\), tada na poziciji \(k\) ne postoji \(z\)-kutija.
Vrednost niza \(z\) na poziciji 0 jednaka je dužini niske jer je kompletna niska uvek prefiks same sebe; međutim ta vrednost se nikada ne koristi.
Primer 6.5.3. \(z\)-niz niske ACBACDACBACBACDA prikazan je na slici 2. Vrednost \(z_6=5\) označava da je podniska ACBAC (koja počinje na poziciji \(6\) i dužine je \(5\)) prefiks niske \(s\), dok podniska ACBACB (koja počinje na istoj poziciji i dužine je \(6\)) nije.
Naredni aplet proverava razumevanje koncepta \(z\)-niza. Za datu nisku upišite vrednosti \(z\)-niza i nakon toga proverite da li ste ih dobro odredili.
Jedno važno pitanje je kako što efikasnije konstruisati \(z\)-niz za datu nisku.
Problem. Za datu nisku \(s\) konstruisati niz \(z\) tako da se na svakoj poziciji \(k\) niza \(z\) nalazi vrednost \(z_k\) jednaka najvećoj dužini podniske niske \(s\) koja počinje na poziciji \(k\) i ujedno je i prefiks niske \(s\) (tj. karakteri niske \(s\) na pozicijama \([0, z_k)\) i \([k, k+z_k)\) se poklapaju).
Direktno rešenje se sastoji u tome da se za svaki indeks iznova traži najduži poklapajući prefiks niske koji počinje na tekućoj poziciji u niski.
vector<int> izracunajZNizTrivijalno(string s) {
int n = s.size();
// inicijalizujemo sve vrednosti z-niza na 0
vector<int> z(n, 0);
for (int k = 1; k < n; k++) {
// sve dok ne izađemo iz opsega niske
// i odgovarajući karakteri se poklapaju
while (k+z[k] < n && s[z[k]] == s[k+z[k]]) {
// inkrementiramo vrednost z-niza na odgovarajucoj poziciji
z[k]++;
}
}
return z;
}Ovo rešenje sadrži dve ugnežđene petlje, a složenost u najgorem slučaju je \(O(n^2)\). Zaista, za nisku AAA...AAA, algoritam grube sile za računanje \(z\)-niza izvršava \(\Theta(n^2)\) koraka. U praksi, očekuje se da se na razlike odgovarajućih karaktera naiđe dosta brže.
\(z\)-algoritam (engl. \(z\)-algorithm) je algoritam za konstrukciju \(z\)-niza složenosti \(O(n)\). Dobio je ime po strukturi podataka koja se njome konstruiše, tj. po \(z\)-nizu. Do njega je prvi došao Gustav Fridrih Hartman 1975. godine, ali je svoju popularnost stekao tek kasnije, nakon što su Martin Eskardo i Rajnard Vilhelm predstavili efikasniju varijantu algoritma. Ideja \(z\)-algoritma jeste da se vrednosti \(z\)-niza izračunavaju iterativno, sleva nadesno, na osnovu prethodno izračunatih vrednosti \(z\)-niza.
U algoritmu se održava par \([l, d]\) koji ograničava \(z\)-kutiju sa najvećom desnom granicom \(d\) od svih do sada pronađenih \(z\)-kutija (tada se segment \(s[l..d]\) poklapa sa prefiksom \(s[0..d-l]\) niske \(s\)). Činjenicu da je \(s[0..d-l]=s[l..d]\) koristićemo za efikasnije računanje vrednosti \(z\)-niza na pozicijama \(l+1,l+2,\ldots,d\).
Dakle, za tekući indeks \(k\) za koji treba izračunati vrednost \(z_k\) moguća su dva slučaja:
\(l<k\leq d\) – tekuća pozicija je unutar opsega \([l, d]\), pa možemo iskoristiti već izračunate vrednosti \(z\)-niza za inicijalizaciju vrednosti \(z_k\) (umesto da krećemo od vrednosti 0). Naime, segmenti \(s[l..d]\) i \(s[0..d-l]\) su jednaki, pa pošto je \(l<k\leq d\), jednaki su i segmenti \(s[k..d]\) i \(s[k-l..d-l]\) pa prilikom računanja vrednosti \(z_k\) možemo krenuti od vrednosti \(z_{k-l}\) koja je već izračunata (slika 3). Međutim, vrednost \(z_{k-l}\) u nekim slučajevima može biti prevelika, jer kada se doda poziciji \(k\) može da bude veća od vrednost indeksa \(d\), a to nije dobro jer mi ne znamo ništa o karakterima niske \(s\) nakon pozicije \(d\). Recimo, u primeru prikazanom na slici 4 vrednost \(z_k\) ne bi bilo ispravno postaviti na \(z_{k-l}=3\) jer bi nas to izvelo van granica opsega \([l,d]\). Dakle, maksimalna dužina poklopljenog dela može biti jednaka broju karaktera od tekuće pozicije \(k\) do poslednje pregledane pozicije \(d\), a to je \(d-k+1\). Stoga se početna vrednost \(z_k\) postavlja na \(z^0_k=\min\{d-k+1, z_{k-l}\}.\) Nakon toga utvrđujemo da li se vrednost \(z_k\) može povećati pokretanjem trivijalnog algoritma od pozicije \(k+z^0_k\).
\(k>d\) – tekuća pozicija \(k\) je van opsega \([l, d]\), pa nemamo nikakvih informacija o poziciji \(k\). Stoga vrednost \(z_k\) računamo trivijalnim algoritmom, tj. poređenjem karakter po karakter niske \(s\) počev od pozicija \(0\) i \(k\);
Dakle, algoritam razmatra dva slučaja koji se razlikuju samo po inicijalizaciji vrednosti \(z[k]\), nakon čega se postupak nastavlja primenom trivijalnog algoritma. Dodatno, ako se nakon inicijalizacije niska \(s[k..k+z[k]]\) cela nalazi u delu tekuće \(z\)-kutije bez njenog poslednjeg karaktera (\(s[l, d)\)), vrednost \(z[k]\) je već konačno određena, pa dalje karaktere ne treba porediti. Ukoliko dođe do poklapanja dela niske počev od pozicije \(k\) sa nekim prefiksom date niske i ako je desna granica preklopljenog segmenta veća od prethodne vrednosti desne granice (\(k+z[k]-1>d\)), ažuriramo granice \([l,d]\) \(z\)-kutije koja se prostire najviše nadesno od svih do tada pronađenih \(z\)-kutija novim granicama \([k,k+z[k]-1]\).
Razmotrimo implementaciju \(z\)-algoritma.
// funkcija koja izracunava sve elemente z-niza
vector<int> izracunajZNiz(const string &s) {
int n = s.size();
// inicijalizujemo sve vrednosti z-niza na 0
vector<int> z(n,0);
int l = 0;
int d = -1;
for (int k = 1; k < n; k++) {
// ako je tekuca pozicija unutar opsega [l,d]
// koristimo prethodno izracunatu vrednost za inicijalizaciju
if (k <= d)
z[k] = min(d-k+1, z[k-l]);
// ako niska s[k..k+z[k]) pripada delu z-kutije bez njenog poslednjeg
// karaktera, vrednost z[k] je vec odredjena
if (z[k] < d-k+1)
continue;
// preskacemo proveru karaktera od pozicije k do pozicije k+z[k]-1;
// od pozicije k+z[k] poredimo karakter po karakter u niski
// i sve dok se karakteri poklapaju povecavamo vrednost z[k]
while (k+z[k] < n && s[z[k]] == s[k+z[k]])
z[k]++;
// ako je nova vrednost desnog kraja najdesnije z-kutije
// veca od prethodne vrednosti, azuriramo interval [l,d]
if (k + z[k] - 1 > d) {
l = k;
d = k + z[k] - 1;
}
}
return z;
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
// funkcija koja izracunava sve elemente z-niza
vector<int> izracunajZNiz(const string &s) {
int n = s.size();
// inicijalizujemo sve vrednosti z-niza na 0
vector<int> z(n,0);
int l = 0;
int d = -1;
for (int k = 1; k < n; k++) {
// ako je tekuca pozicija unutar opsega [l,d]
// koristimo prethodno izracunatu vrednost za inicijalizaciju
if (k <= d)
z[k] = min(d-k+1, z[k-l]);
// ako niska s[k..k+z[k]) pripada delu z-kutije bez njenog poslednjeg
// karaktera, vrednost z[k] je vec odredjena
if (z[k] < d-k+1)
continue;
// preskacemo proveru karaktera od pozicije k do pozicije k+z[k]-1;
// od pozicije k+z[k] poredimo karakter po karakter u niski
// i sve dok se karakteri poklapaju povecavamo vrednost z[k]
while (k+z[k] < n && s[z[k]] == s[k+z[k]])
z[k]++;
// ako je nova vrednost desnog kraja najdesnije z-kutije
// veca od prethodne vrednosti, azuriramo interval [l,d]
if (k + z[k] - 1 > d) {
l = k;
d = k + z[k] - 1;
}
}
return z;
}
vector<int> traziZNiz(const string& niska, const string& tekst) {
vector<int> pojavljivanja;
string zajedno = niska + "#" + tekst;
int n = zajedno.size();
int m = niska.size();
vector<int> zNiz = izracunajZNiz(zajedno);
for (int i = 0; i < n; i++)
if (zNiz[i] == m)
pojavljivanja.push_back(i - m - 1);
return pojavljivanja;
}
int main() {
string uzorak, tekst;
cin >> uzorak >> tekst;
vector<int> pozicije = traziZNiz(uzorak, tekst);
if (pozicije.empty())
cout << -1 << endl;
else {
for (int p : pozicije)
cout << p << " ";
cout << endl;
}
return 0;
}Primetimo da se while petlja može uspešno izvršiti samo kada je \(d-k+1 \leq z_{k-l}\), odnosno kada postoji poklapanje dela niske od pozicije \(k\) do pozicije \(d\) (uključujući i njih) sa nekim prefiksom niske. Kada je \(z_{k-l} < d-k+1\), tada se petlja while može preskočiti. To je urađeno u prethodnom kodu (naredbom continue). U tim slučajevima uslov petlje while nije nikada ispunjen, pa bi algoritam isrpavno radio čak i kada bi se ta naredba continue izostavila.
Pokažimo da je prikazani algoritam linearne vremenske složenosti, iako sadrži dve ugnežđene petlje. Naime, nakon svakog neuspešnog poređenja karaktera u petlji while, tekuća iteracija petlje for se završava. Pošto je ukupan broj iteracija spoljašnje petlje for jednak \(n\), ukupno možemo imati najviše \(n\) nepoklapanja karaktera u petlji while. Svaki karakter niske \(s\) na poziciji \(k+z_k\) koji se uspešno poklopi u unutrašnjoj while petlji, više se nikada ne poredi, te je i broj uspešno poklopljenih karaktera u petlji while maksimalno \(n\). Dakle, u svim iteracijama spoljašnje petlje for, ukupan broj koraka petlje while (provera njenog uslova i izvršavanja njenog tela) je \(O(n)\), te je ukupna složenost algoritma \(O(n)\).
Može se pokazati i da svako izvršavanje tela petlje while povećava desnu granicu segmenta \(d\) najdesnije \(z\)-kutije. Naime, svaka uspešna iteracija petlje while poklapa neki novi karakter niske, desno od granice najdesnije \(z\)-kutije, te se vrednost promenljive \(d\) uvećava za onoliko koliki je broj uspešnih iteracija petlje while. Pošto je maksimalna vrednost za \(d\) jednaka \(n-1\), a početna je jednaka 0, dobijamo da se telo petlje while u svim iteracijama spoljašnje petlje zajedno ukupno neće izvršiti više od \(n-1\) puta. I odavde sledi da je složenost algoritma \(O(n)\).
Primer 6.5.4. Razmotrimo konstrukciju \(z\)-niza za nisku ACBACDACBACBACDA.
Na početku je \([l,d]=[0,0]\), pa vrednosti \(z\)-niza na pozicijama \(1\), \(2\) i \(3\) računamo trivijalnim algoritmom i dobijamo \(z_1=z_2=0, z_3=2\). Nakon izračunate vrednosti \(z_3\) ažuriramo opseg \([l,d]=[3,4]\) (slika 5).
Nakon toga, vrednost \(z\)-niza na poziciji \(k=4\) dobijamo na osnovu vrednosti \(z_{k-l}=z_{4-3}=z_1=0\). Vrednosti \(z_5\) i \(z_6\) dobijamo pokretanjem trivijalnog algoritma (jer za \(k=5\) i \(k=6\) i \(d=4\) važi \(k>d\)) i dobijamo \(z_5=0\), a \(z_6=5\). Pošto za \(k=6\) važi \(k+z_k-1 = 6+5-1 = 10\), desna granica tekuće \(z\)-kutije je veća od prethodne vrednosti \(4\), pa tekući \([l,d]\) opseg najdesnije \(z\)-kutije postaje \([6,10]\) (slika 6).
Nakon ovog koraka, možemo efikasno izračunati naredne vrednosti \(z\)-niza, jer znamo da su niske \(s[0..4]\) i \(s[6..10]\) jednake. Najpre, pošto je \(z_1=z_2=0\) dobijamo i da je \(z_7=z_8=0\). Nakon toga, pošto je \(z_3=2\) i \(d-k+1=10-9+1=2\), znamo da je \(z_9\geq 2\). Pošto nemamo informacije o karakterima niske nakon pozicije \(10\), poredimo segmente dalje karakter po karakter. Ispostavlja se da je \(z_9=7\). Pošto za \(k=9\) važi \(k+z[k]-1 = 9+7-1 = 15\), desna granica tekuće \(z\)-kutije je veća od prethodne vrednosti \(10\), pa je novi \([l,d]\) opseg najdesnije \(z\)-kutije jednak \([9,15]\) (slika 7).
Nakon ovoga, sve preostale vrednosti \(z\)-niza mogu se odrediti na osnovu informacija koje se već nalaze u \(z\)-nizu (slika 8). Obratimo pažnju samo na to da je kod poslednjeg elementa \(z_{15}\) vrednost \(z_{k-l} = z_6 = 5\), međutim, ona je veća od \(d - k + 1 = 1\), pa se zato \(z_{15}\) inicijalizuje na \(d-k+1=1\) umesto na \(z_6=5\) i, pošto se došlo do kraja niza, na toj vrednosti i ostaje.
Naredni aplet ilustruje \(z\)-algoritam.
U ovom poglavlju ćemo prikazati kako se \(z\)-niz upotrebljava za traženje niske u tekstu (traženje podniske uzastopnih karaktera unutar duže niske).
Nekada se prilikom obrade niski konstruiše jedna duža niska koja se sastoji od većeg broja niski razdvojenih specijalnim karakterima. To je slučaj i kod algoritma traženja niske u tekstu zasnovanog na \(z\)-nizu. Naime, u ovom slučaju možemo konstruisati nisku \(p\#t\), gde su niska koja se traži \(p\) i tekst \(t\) razdvojeni specijalnim karakterom \(\#\) koji se ne javlja ni u \(p\) ni u \(t\). \(Z\)-niz niske \(p\#t\) nam može ukazati na to gde se u tekstu \(t\) pojavljuje niska \(p\) jer će takve pozicije imati \(z\)-vrednost jednaku dužini niske \(p\). Dobijene vrednosti \(z\)-niza na pozicijama \(0\) do \(m\), gde je \(m=|p|\) dužina niske \(p\), nisu nam bitne, jer se odnose na pozicije unutar niske \(p\), ali ih je neophodno izračunati u okviru \(z\)-algoritma. Moguće je i izostaviti specijalni karakter \(\#\) i tada bi se u z-nizu tražile pozicije na kojima je vrednost veća ili jednaka dužini niske koju tražimo.
Primer 6.5.5. Razmotrimo slučaj kada je niska \(p = aaba\), a tekst \(t = aabaacaadaabaaba\). Formiramo \(Z\)-niz niske \(p\#t\) (slika 9). Primetimo da su vrednosti \(z\)-niza na pozicijama \(5\), \(14\) i \(17\) jednake \(4\), što je dužina niske \(p\). Pošto je ispred teksta \(t\) dodato \(5\) karaktera (\(4\) karaktera niske \(p\) i specijalni karakter \(\#\)), te pozicije odgovaraju pozicijama \(0\), \(9\) i \(12\) u tekstu i na tim pozicijama u tekstu se javlja niska \(p\).
Složenost ovog algoritma je \(O(m+n)\), gde je \(m=|p|\) dužina niske \(p\), a \(n=|t|\) dužina teksta \(t\), jer se algoritam svodi na konstrukciju \(z\)-niza niske \(p\#t\) (za koju smo videli da je linearne složenosti u odnosu na dužinu niza) i prolazak kroz njegove vrednosti.
vector<int> traziZNiz(const string& niska, const string& tekst) {
vector<int> pojavljivanja;
string zajedno = niska + "#" + tekst;
int n = zajedno.size();
int m = niska.size();
vector<int> zNiz = izracunajZNiz(zajedno);
for (int i = 0; i < n; i++)
if (zNiz[i] == m)
pojavljivanja.push_back(i - m - 1);
return pojavljivanja;
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
// funkcija koja izracunava sve elemente z-niza
vector<int> izracunajZNiz(const string &s) {
int n = s.size();
// inicijalizujemo sve vrednosti z-niza na 0
vector<int> z(n,0);
int l = 0;
int d = -1;
for (int k = 1; k < n; k++) {
// ako je tekuca pozicija unutar opsega [l,d]
// koristimo prethodno izracunatu vrednost za inicijalizaciju
if (k <= d)
z[k] = min(d-k+1, z[k-l]);
// ako niska s[k..k+z[k]) pripada delu z-kutije bez njenog poslednjeg
// karaktera, vrednost z[k] je vec odredjena
if (z[k] < d-k+1)
continue;
// preskacemo proveru karaktera od pozicije k do pozicije k+z[k]-1;
// od pozicije k+z[k] poredimo karakter po karakter u niski
// i sve dok se karakteri poklapaju povecavamo vrednost z[k]
while (k+z[k] < n && s[z[k]] == s[k+z[k]])
z[k]++;
// ako je nova vrednost desnog kraja najdesnije z-kutije
// veca od prethodne vrednosti, azuriramo interval [l,d]
if (k + z[k] - 1 > d) {
l = k;
d = k + z[k] - 1;
}
}
return z;
}
vector<int> traziZNiz(const string& niska, const string& tekst) {
vector<int> pojavljivanja;
string zajedno = niska + "#" + tekst;
int n = zajedno.size();
int m = niska.size();
vector<int> zNiz = izracunajZNiz(zajedno);
for (int i = 0; i < n; i++)
if (zNiz[i] == m)
pojavljivanja.push_back(i - m - 1);
return pojavljivanja;
}
int main() {
string uzorak, tekst;
cin >> uzorak >> tekst;
vector<int> pozicije = traziZNiz(uzorak, tekst);
if (pozicije.empty())
cout << -1 << endl;
else {
for (int p : pozicije)
cout << p << " ";
cout << endl;
}
return 0;
}