Heširanje niski (engl. string hashing) podrazumeva da se svakoj niski dodeli ceo broj iz određenog opsega. Iako ne može da se garantuje da će svakoj niski biti dodeljen različiti broj, verovatnoća da su dve niske predstavljene istim brojem treba da bude jako mala. Na taj način se problem poređenja dugačkih niski može svesti na poređenje brojeva koji ih reprezentuju, što je mnogo efikasnija operacija. Ako brojevi kojim su predstavljene niske nisu jednaki, onda niske sigurno nisu jednake. Ako su brojevi jednaki, polazne niske su gotovo izvesno jednake (ako želimo da budemo baš apsolutno sigurni, možemo ih eksplicitno uporediti). Na primer, ako želimo da uporedimo da li su dve velike datoteke (na primer, knjige u PDF formatu ili video-zapisi isti), možemo uporediti samo njihove heš-vrednosti.
Tehnika heširanja niski je dobila na popularnosti kada su Rabin i Karp osmislili efikasan algoritam za traženje jedne niske u drugoj (proveru da li se jedna niska javlja kao podniska tj. segment uzastopnih karaktera druge) zasnovan na heširanju. Algoritmi heširanja mogu biti korisni i u rešavanju nekih drugih problema nad tekstom, kao što su određivanje broja različitih podniski date niske, pronalaženje najduže niske koja se javlja bar dva puta kao podniska date niske, kompresija niske, određivanje broja palindromskih podniski u datoj niski i dr.
Heširanje ima primenu u raznim domenima.
U kriptografiji se definišu kriptografske heš-funkcije (na primer, SHA, MD5) koje pored uobičajenih svojstava heš-funkcija imaju i dodatna sigurnosna svojstva (na primer, iako se zna algoritam heširanja, složenost pronalaženja niske koja bi bila predstavljena datom heš-vrednošću je ogromna i ovaj zadatak je praktično neizvodiv). Jedna od uobičajenih primena kriptografskih heš-funkcija je u sistemima za proveru lozinki. Naime, iz bezbedonosnih razloga, lozinke se obično čuvaju u heširanom obliku (jer u slučaju da neko uspe da dobije neovlašćeni pristup sistemu, on neće moći da sazna stvarne lozinke, već samo njihove heš-vrednosti na osnovu kojih je gotovo nemoguće rekonstruisati originalne lozinke). Kada korisnik unese lozinku, računa se njena heš-vrednost i upoređuje sa onom sačuvanom. Ako se te dve heš-vrednosti ne poklope, tada je sigurno uneta pogrešna lozinka. Ako se poklope, postoji izvesna verovatnoća da je uneta lozinka pogrešna (jer heš-funkcije nisu injektivne), međutim, heš-funkcije se prave tako da ta verovatnoća bude jako mala (smatra se da je veća verovatnoća da hardver pogrešno izračuna neku heš-vrednost nego da neka nasumično odabrana lozinka ima istu heš-vrednost kao prava lozinka).
Heširanje se koristi i za obezbeđivanje integriteta poruke koja se šalje putem kanala za komunikaciju. Provera da li je poslata poruka neizmenjena se vrši poređenjem heš vrednosti poruke pre i posle slanja: ako su ove dve vrednosti jednake, smatramo da je prenos uspešno završen. Često se prilikom preuzimanja dokumenata sa interneta (na primer, instalacionih datoteka) pored dokumenata na sajtu navode i njihove heš-vrednosti da bi korisnik bio siguran da je preuzeo dokumente koji nisu u međuvremenu izmenjeni.
Heš-vrednosti se koriste i prilikom digitalnog potpisa. Umesto da se čitav dokument potpisuje tajnim ključem (što može biti veoma neefikasno), izračunava se njegova heš-vrednost koja se potpisuje. Heš-vrednost garantuje i da nije došlo do izmena dokumenta nakon njegovog potpisivanja.
Heširanje ima primenu i u prevodiocima programskih jezika. Naime, većina programskih jezika ima veliki broj rezervisanih reči, poput ključnih reči if, for i while, koje je potrebno obraditi na drugačiji način od ostalih identifikatora. Kako bi utvrdio da li je pročitana reč iz izvornog koda rezervisana, prevodilac čuva heširane vrednosti rezervisanih reči tog programskog jezika.
Prilikom heširanja, niski \(s\) se korišćenjem neke heš-funkcije (engl. hash function) \(h\) pridružuje heš-vrednost (engl. hash value) \(h(s)\) koja obično pripada nekom intervalu prirodnih brojeva \([0, m)\). Heš-funkcija zadovoljava naredni uslov: ako su dve niske \(s\) i \(t\) jednake, i njihove heš-vrednosti \(h(s)\) i \(h(t)\) su jednake. Naime, heš-funkcija je uvek deterministička – za jedan ulaz uvek daje jedan isti izlaz. Sa druge strane, heš-funkcija ne mora biti injektivna: ako je \(h(s)=h(t)\), ne mora da važi \(s=t\). Situacija kada za dve različite niske \(s\) i \(t\) važi \(h(s) = h(t)\) naziva se kolizija (engl. collision).
Pošto je broj različitih niski koje je moguće heširati obično jako veliki, heš-funkcije gotovo nikada nisu injektivne i kolizije je nemoguće izbeći. Na primer, ako bismo hteli da vrednosti heš-funkcije budu jedinstvene za svaku nisku dužine do 14 karaktera koja se sastoji samo od malih slova engleske abecede, potrebno bi nam bilo \(1 + 26^1 + \ldots + 26^{14} = \frac{26^{15} - 1}{26 - 1}\) različitih heš-vrednosti, što je oko \(26^{14}\). Pošto je \(26^{14} > 2^{64}\), te heš-vrednosti ne bi stale u opseg 64-bitnih celih brojeva, što je najširi primitivni celobrojni tip podataka. U praksi obično razmatramo i mnogo duže niske i širi skup karaktera i jasno je da čak ni sa povećanjem broja bitova (danas se često koriste heš-vrednosti predstavljene pomoću 256 bitova) injektivnost nije moguće postići.
Poželjno je da heš-funkcija bude surjektivna na svom kodomenu \([0, m)\) kao i da verovatnoća da heš-vrednosti dve različite niske budu jednake, odnosno da dođe do kolizije, bude što je moguće manja. U velikom broju slučajeva ta je verovatnoća toliko mala, da se mogućnost dolaska do kolizije ignoriše, čime se teorijski narušava korektnost algoritma. Moguće je, pak, da se u slučajevima kada se dobiju jednake heš-vrednosti dve niske, proveri jednakost ove dve niske karakter po karakter. Time se garantuje tačnost, ali se potencijalno žrtvuje efikasnost algoritma. Da li će se ta provera vršiti zavisi od toga da li je primena takva da je u redu tolerisati jako malu verovatnoću netačnog odgovora.
Prilikom heširanja dve fiksirane niske obično ne dolazi do kolizije (tj. ne dešava se da dve različite niske imaju istu heš-vrednost). Na primer, za odabir vrednosti parametra \(m=10^9\) (što odgovara heš-vrednostima od tridesetak bitova), pod pretpostavkom da su sve heš-vrednosti jednako verovatne, verovatnoća da dođe do kolizije je samo \(1/m=10^{-9}\). Međutim, ukoliko jednu fiksiranu nisku \(s\) poredimo sa \(10^6\) drugih različitih niski, verovatnoća da dođe do bar jedne kolizije iznosi oko \(10^6\cdot 10^{-9}=10^{-3}\), dok ako poredimo \(10^6\) niski međusobno verovatnoća da dođe do bar jedne kolizije je skoro jednaka 1.1
Postoji jednostavni “trik” kojim se može smanjiti verovatnoća da do kolizije dođe – računanjem vrednosti dve različite heš-funkcije (štaviše, može se iskoristiti i ista heš-funkcija za različite vrednosti svojih parametara). Ako je vrednost parametra \(m\) oko \(10^9\) za obe heš-funkcije, onda je ovo uporedivo sa korišćenjem jedne heš-funkcije za vrednost parametra \(m\) koja je približno jednaka \(10^{18}\). Sada, ako poredimo \(10^6\) niski međusobno, verovatnoća da dođe do kolizije smanjiće se na \((10^6\cdot 10^6)\cdot 10^{-18}=10^{-6}\).
Heširanje se često koristi da bi se algoritmi grube sile učinili efikasnijim. Razmotrimo problem upoređivanja dve niske \(s\) i \(t\). Algoritam grube sile poredi date niske \(s\) i \(t\) karakter po karakter i složenosti je \(O(\min\{|s|, |t|\})\), gde su \(|s|\) i \(|t|\) dužine niski \(s\) i \(t\) redom. Postavlja se pitanje da li postoji efikasniji algoritam za poređenje niski \(s\) i \(t\). Svaku od niski \(s\) i \(t\) možemo heširati i preslikati u celobrojnu vrednost i umesto niski uporediti dobijene celobrojne vrednosti. Upoređivanje niski svođenjem na upoređivanje njihovih heš-vrednosti je složenosti \(O(1)\). Međutim, ne treba zanemariti činjenicu da je samo heširanje niski \(s\) i \(t\), kao što ćemo uskoro videti, složenosti \(O(|s|+|t|)\).
U jeziku C++ na raspolaganju nam je struktura hash, koja se može upotrebiti za računanje heš-vrednosti niski (ali i heš-vrednosti ostalih osnovnih tipova podataka).
hash<string> h;
cout << h("abrakadabra") << endl;Ipak, u većini narednih algoritama koristićemo heš-funkcije koje ćemo sami definisati.
Jasno je da heš-funkcija treba da zavisi od multiskupa karaktera koji se javljaju u niski i od redosleda karaktera u niski. Niske maja i mara bi trebalo da imaju različite heš-vrednosti, kao i niske maja i jama. Dobar i široko rasprostranjen način definisanja heš-funkcije niske \(s\) dužine \(n\) je korišćenjem polinomske heš-funkcije (engl. polynomial rolling hash function). Ona dolazi u varijanti sleva-nadesno i zdesna-nalevo.
Polinomska heš-funkcija sleva-nadesno za nisku \(s\) dužine \(n\) se definiše na sledeći način:
\[ \begin{array}{rcl} h(s) &=& (s[0]\cdot p^{n-1}+s[1]\cdot p^{n-2}+\ldots+s[n-1]p^0)\,\mathrm{mod}\,m \\ &=& (\displaystyle\sum_{i=0}^{n-1}s[i]\cdot p^{n-i-1})\,\mathrm{mod}\,m, \end{array} \](1)
pri čemu je \(s[i]\) celobrojni kôd \(i\)-tog karaktera niske \(s\), a \(p\) i \(m\) su neki unapred odabrani, pozitivni brojevi. Primetimo da prethodna definicija polinomske heš-funkcije odgovara predstavljanju “broja” \(s\) u brojevnom sistemu sa osnovom \(p\) (uz određivanje ostatka pri deljenju dobijene vrednosti sa sa \(m\) na kraju).
Potrebno je svaki karakter niske \(s\) kodirati celim brojem. Na primer, kada se kodiraju samo mala slova engleske abecede, moguće je koristiti sledeće kodiranje: \(a\rightarrow 1, b\rightarrow 2, \ldots, z\rightarrow 26\). Ono se može implementirati na sledeći način:
// funkcija koja izracunava kod datog karaktera: a->1, b->2, ..., z->26
int kod(char c) {
return c - 'a' + 1;
}Pridruživanje koda 0 nekom karakteru (na primer, \(a\rightarrow 0\)), nije pogodno jer bi onda vrednosti heš-funkcije svih niski koje se sastoje od tog karaktera (na primer, a, aa, aaa, aaaa, \(\ldots\)) bile jednake 0, dok bi niske od kojih se jedna dobija dodavanjem nekoliko tih karaktera na početak druge (na primer, niske na i ana) imale istu vrednost heš-funkcije.
Pažljiv odabir parametara \(p\) i \(m\) je važan da bi se osigurala dobra svojstva heš-funkcije. Često se za \(p\) bira prvi prost broj veći od broja karaktera u ulaznoj azbuci. Na primer, ako se niske sastoje samo od malih slova engleske abecede, onda je dobar izbor \(p=31\). Naime, pokazuje se da kada je vrednost parametra \(p\) manja od veličine azbuke, onda je p kôd nekog mogućeg karaktera niske i lako je pronaći dve niske već dužine 2 kod kojih se javlja kolizija (na primer, to mogu biti niske čiji su kodovi karaktera [2, 0] i [1, p]). Poželjno je, takođe, da vrednost parametra \(m\) bude neki veliki broj, jer je verovatnoća da dve slučajno odabrane niske imaju istu heš-vrednost približno jednaka \(1/m\). Ipak, izbegavaćemo prevelike vrednosti za parametar \(m\), jer je pogodno da vrednosti \(m\cdot m\) i \(p\cdot m\) ne izazivaju prekoračenje (što ćemo obrazložiti nešto kasnije).
Kao i za parametar \(p\), i za parametar \(m\) je pogodno birati neki prost broj. Prosti brojevi se koriste da se ne bi dešavao veliki broj kolizija kada skup niski koje se heširaju ispoljava određena matematička svojstva (na primer kada su kodovi svih karaktera koji se javljaju u tom skupu umnošci istog broja, recimo parni brojevi). U narednim primerima za vrednost parametra \(m\) biraćemo prost broj \(10^9+9\). On je manji od \(2^{30}\), pa vrednost \(m\cdot m\) staje u 64-bitni ceo broj. Primetimo i sledeće: kada izračunavanja ne bismo vršili po modulu \(m\), odnosno ako u definiciji polinomske heš-funkcije ne bi figurisala vrednost \(m\), onda bi se, usled prekoračenja, operacije vršile po modulu broja podržanih vrednosti odgovarajućeg celobrojnog tipa (dakle po modulu \(2^{32}\) ili \(2^{64}\)).
Broj različitih niski raste jako brzo, pa se i za skupove veoma kratkih niski može garantovati postojanje kolizije. Na primer, ako za \(m=10^9+9\) razmotrimo skup niski sastavljenih od malih slova engleske abecede, takvih da je dužina niske manja ili jednaka 7, ukupan broj ovakvih niski iznosi: \(26^0+26^1+26^2+26^3+26^4+26^5+26^6+26^7=8353082583 > 10^9+9=m\). U ovoj situaciji garantovano je postojanje kolizije.
Izračunavanje heš-vrednosti se na osnovu definisane polinomske heš-funkcije sprovodi primenom Hornerove šeme i linearne je složenosti \(O(|s|)\) u odnosu na dužinu niske \(|s|\). Implementacija u jeziku C++ može biti sledeća:
long long izracunajHesVrednost(const string &s) {
int p = 31;
int m = 1e9 + 9;
// vrednost hes-funkcije niske s racunamo u duhu Hornerove sheme
long long h = 0;
for (int i = 0; i < s.size(); i++) {
h = (h * p + kod(s[i])) % m;
}
return h;
}Da bi se račun sveo na manje brojeve, u funkciji za računanje heš-vrednosti niske \(s\) dužine \(n\) međurezultati su računati po modulu \(m\), odnosno razmatran je niz međuvrednosti \(h_i\) za \(i=0,1,\ldots,n\), koji odgovara heš-vrednostima prefiksa niske \(s\) dužine \(i\).
\[\begin{eqnarray*} h_{0}&=&0 \\ h_{i+1}&=&(h_{i}\cdot p+s[i])\,\mathrm{mod}\,m, \ \ 0\leq i < n \nonumber \end{eqnarray*}\]
Konačna heš-vrednost je vrednost \(h_{n}\).
Računanje međurezultata po modulu \(m\) matematički je korektno na osnovu pravila modularne aritmetike.
Primetimo da pošto je \(h_i<m\), \(s[i] < p\) i pošto \(p\cdot m\) ne izaziva prekoračenje, prilikom izračunavanja vrednosti \(h_{i+1}\) ne dolazi do prekoračenja.
Ova polinomska heš-funkcija ima svojstvo da joj se vrednost može lako ažurirati kada se simboli dodaju ili uklanjaju sa krajeva niske (odatle potiče termin rolling u engleskom nazivu). Naime, ako poznajemo heš-vrednost niske \(s_is_{i+1}\ldots s_{i+n-1}\), tada lako možemo izračunati heš-vrednost niske \(s_{i+1}s_{i+2}\ldots s_{i+n}\). Prva vrednost je jednaka \(h_i = (s[i]\cdot p^{n-1}+s[i+1]\cdot p^{n-2}+\ldots+s[i+n-1])\,\mathrm{mod}\,m\), a druga \(h_{i+1} = (s[i+1]\cdot p^{n-1}+s[i+2]\cdot p^{n-2}+\ldots+s[i+n])\,\mathrm{mod}\,m\), pa je
\[h_{i+1} = \left((h_i - s[i]p^{n-1})\cdot p + s[i+n]\right)\,\mathrm{mod}\,m.\](2)
Polinomska heš-funkcija zdesna-nalevo niske \(s\) se definiše na sledeći način:
\[ \begin{array}{rcl} h'(s) &=& (s[0]+s[1]\cdot p+\ldots+s[n-1]\cdot p^{n-1})\,\mathrm{mod}\,m \\ &=& (\sum_{i=0}^{n-1}s[i]\cdot p^{i})\,\mathrm{mod}\,m \end{array} \](3)
kod koje je, nasuprot prethodno definisanoj heš-funkciji, najmanji stepen broja \(p\) uz prvi karakter niske \(s\), a najveći uz poslednji karakter niske.
Za izračunavanje ove varijante heš-funkcije, poželjno je razmatrati niz \(h_i'\) za \(i=n,n-1,\ldots,0\), koji odgovara heš-vrednostima sufiksa niske \(s\) dužine \(n-i\), pri čemu je cilj izračunati vrednost \(h_{0}'\):
\[\begin{eqnarray*} h_{n}'&=&0 \\ h_{i}'&=&(h_{i+1}'\cdot p+s[i])\,\mathrm{mod}\,m, \ \ 0\leq i < n \end{eqnarray*}\]
U jeziku C++ implementacija može biti sledeća:
long long izracunajHesVrednost(const string &s) {
int p = 31;
int m = 1e9 + 9;
// vrednost hes-funkcije niske s racunamo u duhu Hornerove sheme
// razmatranjem karaktera niske u obratnom poretku
long long h = 0;
for (int i = s.size() - 1; i >= 0; i--) {
h = (h * p + kod(s[i])) % m;
}
return h;
}I ova polinomska heš-funkcija ima svojstvo da joj se vrednost može lako ažurirati kada se simboli dodaju ili uklanjaju sa krajeva niske. Naime, ako poznajemo heš-vrednost niske \(s_is_{i+1}\ldots s_{i+n-1}\), tada lako možemo izračunati heš-vrednost niske \(s_{i+1}s_{i+2}\ldots s_{i+n}\). Prva vrednost je jednaka \(h_i = (s[i]+s[i+1]\cdot p+\ldots+s[i+n-1]\cdot p^{n-1})\,\mathrm{mod}\,m\), a druga \(h_{i+1} = (s[i+1]+s[i+2]\cdot p+\ldots+s[i+n]\cdot p^{n-1})\,\mathrm{mod}\,m\), pa je
\[h_{i+1} = \left(\frac{h_i - s[i]}{p} + s[i+n]\cdot p^{n-1}\right) \,\mathrm{mod}\,m.\]
Umesto deljenja sa \(p\), moguće je vršiti množenje modularnim inverzom broja \(p\) po modulu \(m\).
Dato je \(n\) niski \(s_1,s_2,\ldots, s_n\). Pronaći sve duplikate među njima i podeliti ovaj niz niski u grupe jednakih niski. Za svaku grupu odrediti indekse niski te grupe u polaznom nizu.
Sa standardnog ulaza se učitava \(n \leq 10000\) niski dužine najviše \(m \leq 10000\). Niske su sastavljene samo od malih slova engleske abecede.
Za svaku grupu ispisati indekse niski iz te grupe u polaznom nizu.
ana a dvorana ana banana ana kopakabana banana
2 1 4 6 5 8 3 7
Direktan pristup sastoji se u poređenju svake niske sa svakom drugom: poređenje dve niske maksimalne dužine \(m\) karakter po karakter je u najgorem slučaju je složenosti \(O(m)\) (doduše, može se očekivati da se najgori slučaj ne dešava često tj. da će se različitost dve niske ustanoviti već nakon gledanja njihovih nekoliko početnih karaktera). Ukupan broj poređenja niski je reda \(O(n^2)\), te je ukupna složenost odgovarajućeg algoritma \(O(n^2m)\).
Efikasnije rešenje dobija se sortiranjem svih niski i traženjem duplikata u sortiranom nizu. Sortiranje niski uključuje \(O(n\log n)\) upoređivanja niski, a svako poređenje niski je u najgorem slučaju složenosti \(O(m)\), te je ukupna složenost sortiranja niski jednaka \(O(nm\log n)\). Dodatno, prolazak kroz skup niski u sortiranom redosledu i identifikovanje istih niski je složenosti \(O(nm)\), te je ukupna složenost ovog algoritma \(O(nm\log n)\).
Pristup zasnovan na heširanju niski redukuje vreme poređenja dve niske na \(O(1)\) (pod pretpostavkom da ne proveravamo da li je došlo do kolizije). Na taj način dobijamo algoritam složenosti \(O(nm+n\log n)\), gde složenost \(O(nm)\) potiče od računanja heš-vrednosti svih niski, a \(O(n\log n)\) od sortiranja niski na osnovu njihovih heš-vrednosti. Dodatno, prolazak kroz heš-vrednosti niski u sortiranom poretku i identifikovanje istih niski je složenosti \(O(n)\). Ako želimo da budemo sigurni u ispravnost algoritma, kada su heš-vrednosti nekih niski jednake, potrebno je eksplicitno uporediti te niske, za šta je u najgorem slučaju, kada su sve heš-vrednosti jednake, potrebno \(n^2\) poređenja niski, koja zahtevaju vreme \(O(m)\), što zahteva dodatno vreme \(O(n^2m)\). Međutim, realno je očekivati da su grupe jednakih heš-vrednosti mnogo manje i da će ovo vreme biti mnogo manje.
Implementacija u jeziku C++ je data u nastavku. U njoj se ne proverava postojanje kolizija tj. pretpostavlja se da jednakim heš-vrednostima odgovaraju jednake niske.
vector<vector<int>> grupisiIsteNiske(const vector<string> &niske) {
// broj niski
int n = niske.size();
// vektor parova hash vrednosti i pozicije niske u polaznom nizu
vector<pair<long long, int>> h(n);
// izracunavamo hash vrednost svake niske;
// uz hes vrednost niske cuvamo i njen indeks u polaznom nizu
for (int i = 0; i < n; i++)
h[i] = {izracunajHesVrednost(niske[i]), i+1};
// sortiramo niz hes vrednosti
sort(h.begin(),h.end());
// svaki element vektora sadrzi niz indeksa niski
// koje su medjusobno jednake
vector<vector<int>> grupe;
// prolazimo skupom svih niski u sortiranom poretku
for (int i = 0; i < n; i++){
// ukoliko se radi o prvoj niski u sortiranom poretku
// ili o niski koja nije jednaka prethodnoj u sortiranom poretku
// onda je potrebna nova grupa
if (i == 0 || h[i].first != h[i-1].first) {
vector<int> novaGrupa;
grupe.push_back(novaGrupa);
}
// u poslednju (tekucu) grupu dodajemo na kraj indeks niske
// koja ima tekucu hash vrednost
grupe.back().push_back(h[i].second);
}
return grupe;
}#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long izracunajHesVrednost(const string &s) {
int p = 31;
int m = 1e9 + 9;
// vrednost hes-funkcije niske s racunamo u duhu Hornerove sheme
// razmatranjem karaktera niske u obratnom poretku
long long h = 0;
for (int i = s.size() - 1; i >= 0; i--)
h = (h * p + (s[i] - 'a' + 1)) % m;
return h;
}
vector<vector<int>> grupisiIsteNiske(const vector<string> &niske) {
// broj niski
int n = niske.size();
// vektor parova hash vrednosti i pozicije niske u polaznom nizu
vector<pair<long long, int>> h(n);
// izracunavamo hash vrednost svake niske;
// uz hes vrednost niske cuvamo i njen indeks u polaznom nizu
for (int i = 0; i < n; i++)
h[i] = {izracunajHesVrednost(niske[i]), i+1};
// sortiramo niz hes vrednosti
sort(h.begin(),h.end());
// svaki element vektora sadrzi niz indeksa niski
// koje su medjusobno jednake
vector<vector<int>> grupe;
// prolazimo skupom svih niski u sortiranom poretku
for (int i = 0; i < n; i++){
// ukoliko se radi o prvoj niski u sortiranom poretku
// ili o niski koja nije jednaka prethodnoj u sortiranom poretku
// onda je potrebna nova grupa
if (i == 0 || h[i].first != h[i-1].first) {
vector<int> novaGrupa;
grupe.push_back(novaGrupa);
}
// u poslednju (tekucu) grupu dodajemo na kraj indeks niske
// koja ima tekucu hash vrednost
grupe.back().push_back(h[i].second);
}
return grupe;
}
int main() {
vector<string> niske;
string niska;
while (cin >> niska)
niske.push_back(niska);
vector<vector<int>> grupe = grupisiIsteNiske(niske);
// stampamo niske po grupama
for (int i = 0; i < grupe.size(); i++) {
for (int j = 0; j < grupe[i].size(); j++)
cout << grupe[i][j] << " ";
cout << endl;
}
return 0;
}Rabin i Karp su 1987. godine predložili algoritam koji rešava problem traženja niske (engl. pattern) u tekstu (engl. text) korišćenjem tehnike heširanja niski.
Problem. Za dati tekst \(t=t_0t_1\ldots t_{N-1}\) i nisku \(p=p_0p_1\ldots p_{M-1}\) odrediti sve podniske uzastopnih elemenata (segmente) niske \(t\) koje su jednake \(p\).
Ideja Rabin-Karpovog algoritma je sledeća: korišćenjem polinomske heš-funkcije izračunati heš-vrednost niske \(p\) i svih segmenata teksta \(t\), koji imaju dužinu \(|p|=M\) i uporediti njihove vrednosti. Ako se heš-vrednost niske i segmenta ne poklopi, tekući segment se sigurno ne poklapa sa podniskom koju tražimo i prelazi se na naredni segment. Ako se heš-vrednosti poklope, tada treba izvršiti eksplicitnu proveru da li se tekući segment poklapa sa podniskom koju tražimo. Na početku izračunavamo heš-vrednost početne podniske teksta dužine \(M\). U svakom koraku ovu vrednost inkrementalno ažuriramo (u slučaju kada je heš-funkcija zadata formulom (1) ažuriranje vršimo na osnovu formule 2).
Razmotrimo implementaciju Rabin-Karpovovog algoritma.
// Rabin-Karpov algoritam za trazenje niske u tekstu
vector<int> traziRabinKarp(const string &niska, const string &tekst) {
int M = niska.size();
int N = tekst.size();
// vektor pocetnog indeksa pojavljivanja niske u tekstu
vector<int> pozicije;
// ako je tekst kraci od niske, on je ne sadrzi
if (M > N) return pozicije;
int p = 31;
int m = 1e9 + 9;
// p^(M-1) mod m
long long pS = stepen(p, M-1, m);
// racunamo hes-vrednost date niske
long long hesNiske = 0;
for (int i = 0; i < M; i++)
hesNiske = (hesNiske*p + kod(niska[i])) % m;
// racunamo hes-vrednost pocetnih M karaktera teksta
long long hesSegmenta = 0;
for (int i = 0; i < M; i++)
hesSegmenta = (hesSegmenta*p + kod(tekst[i])) % m;
// proveravamo sve pocetne pozicije niske unutar teksta
for (int i = 0; i <= N - M; i++) {
// ako se poklapaju hesh vrednosti segmenta teksta i niske
if (hesSegmenta == hesNiske)
// eksplicitna provera poklapanja
if (niska == tekst.substr(i, M))
pozicije.push_back(i);
// azuriramo hes-segmenta
if (i < N - M)
hesSegmenta = ((hesSegmenta - kod(tekst[i])*pS + m)*p + kod(tekst[i + M])) % m;
}
return pozicije;
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
long long stepen(long long x, int k, int m) {
if (k == 0)
return 1;
if (k % 2 == 0)
return stepen((x * x) % m, k / 2, m);
return (x * stepen(x, k-1, m)) % m;
}
// funkcija koja izracunava kod datog karaktera
int kod(char c) {
return c - 'a' + 1;
}
// Rabin-Karpov algoritam za trazenje niske u tekstu
vector<int> traziRabinKarp(const string &niska, const string &tekst) {
int M = niska.size();
int N = tekst.size();
// vektor pocetnog indeksa pojavljivanja niske u tekstu
vector<int> pozicije;
// ako je tekst kraci od niske, on je ne sadrzi
if (M > N) return pozicije;
int p = 31;
int m = 1e9 + 9;
// p^(M-1) mod m
long long pS = stepen(p, M-1, m);
// racunamo hes-vrednost date niske
long long hesNiske = 0;
for (int i = 0; i < M; i++)
hesNiske = (hesNiske*p + kod(niska[i])) % m;
// racunamo hes-vrednost pocetnih M karaktera teksta
long long hesSegmenta = 0;
for (int i = 0; i < M; i++)
hesSegmenta = (hesSegmenta*p + kod(tekst[i])) % m;
// proveravamo sve pocetne pozicije niske unutar teksta
for (int i = 0; i <= N - M; i++) {
// ako se poklapaju hesh vrednosti segmenta teksta i niske
if (hesSegmenta == hesNiske)
// eksplicitna provera poklapanja
if (niska == tekst.substr(i, M))
pozicije.push_back(i);
// azuriramo hes-segmenta
if (i < N - M)
hesSegmenta = ((hesSegmenta - kod(tekst[i])*pS + m)*p + kod(tekst[i + M])) % m;
}
return pozicije;
}
int main() {
string uzorak, tekst;
cin >> uzorak >> tekst;
vector<int> pozicije = traziRabinKarp(uzorak, tekst);
if (pozicije.empty())
cout << -1 << endl;
else {
for (int p : pozicije)
cout << p << " ";
cout << endl;
}
}Izračunavanje heš-vrednosti niske koju tražimo i početnog segmenta teksta se može uraditi u vremenu \(O(M)\). Nakon toga \(O(N)\) puta ažuriramo heš-vrednost segmenta u vremenu \(O(1)\) (pretpostavljajući da je stepen \(p^{M-1} \,\mathrm{mod}\,m\) jedno izračunat, što može biti urađeno u vremenu \(O(\log{M})\) algoritmom brzog stepenovanja). Ako se niska ne javlja u tekstu, tada je složenost prethodnog postupka \(O(M+N)\). Međutim, svaki put kada se heš-vrednosti poklope, vrši se eksplicitna provera jednakosti niski, koja zahteva vreme \(O(M)\). Pošto se u veoma specijalnim slučajevima niska može javljati unutar podniske \(O(N)\) puta, te eksplicitne provere zahtevaju vreme \(O(MN)\), što je zapravo složenost najgoreg slučaja Rabin-Karpovog algoritma i on po tome nije bolji od naivnog algoritma. Ipak, za očekivati je da će se algoritam primenjivati u problemima pretrage običnih tekstualnih dokumenata kada se podniska u tekstu javlja obično samo \(O(1)\) puta i tada je složenost Rabin-Karpovog algoritma samo \(O(M+N)\), što je mnogo efikasnije od naivnog algoritma.
U nekim primenama je potrebno izračunavati heš-vrednosti većeg broja različitih segmenata date niske. To se može efikasno uraditi ako se izračunaju heš-vrednosti svih prefiksa niske (ideja je slična izračunavanja zbirova segmenata na osnovu poznatih zbirova prefiksa niza).
Problem. Data je niska \(s\) dužine \(n\). Napisati algoritam kojim se za date parove indeksa \(i\) i \(j\) (njih ukupno \(q\)) za koje važi \(0\leq i\leq j<n\), efikasno izračunavaju heš-vrednosti podniski \(s[i..j]\) polazne niske (podniske su segmenti susednih karaktera polazne niske \(s\) od pozicije \(i\) zaključno sa pozicijom \(j\)).
Primer 5.4.1. Za nisku \(s\) koja je jednaka ananas i za vrednosti \(i=1\) i \(j=4\), potrebno je izračunati heš-vrednost niske nana.
Razmotrimo najpre prvu varijantu polinomske heš-funkcije koja je zadata formulom (1). Prema definiciji heš-funkcije važi:
\[\begin{eqnarray*}\label{eq:hash_segment} h(s[i..j]) &=& (s[i]\cdot p^{j-i}+s[i+1]\cdot p^{j-i-1}+\ldots+s[j]) \,\mathrm{mod}\,m \nonumber \\ &=& \left(\sum_{k=i}^{j}s[k]\cdot p^{j-k}\right) \,\mathrm{mod}\,m \end{eqnarray*}\]
Ova vrednost može se direktno izračunati algoritmom vremenske složenosti \(O(j-i)\), odnosno u najgorem slučaju je složenosti \(O(|s|)\), gde je \(|s|\) dužina niske \(s\). Da bi se naivnim pristupom izračunala vrednost za \(q\) segmenata, potrebno je vreme \(O(q\cdot |s|)\). Da li možemo efikasnije rešiti ovaj problem?
Upotrebimo ideju prefiksnih suma, koja omogućuje da se zbir svakog segmenta niza može izraziti kao razlika dva zbira prefiksa. Definišimo niz \(H_k\) tako da je \(H_0 = 0\), a \(H_k = h(s[0..k-1])\). Zapišimo čemu su jednake heš-vrednosti prefiksa niske \(s\) dužina redom \(j+1\) i \(i\):
\[\begin{eqnarray*} H_{j+1} = h(s[0..j])&=&(s[0]\cdot p^j+s[1]\cdot p^{j-1}+\ldots+s[j]) \,\mathrm{mod}\,m, \\ H_i = h(s[0..i-1])&=&(s[0]\cdot p^{i-1}+s[1]\cdot p^{i-2}+\ldots+s[i-1]) \,\mathrm{mod}\,m. \end{eqnarray*}\]
Pri tom smatramo da je \(h(s[0..-1]) = 0\) (što može da se desi za \(i=0\)). Primetimo da je:
\[ \begin{array}{rcl} h(s[i..j]) &=& (s[i]\cdot p^{j-i}+s[i+1]\cdot p^{j-(i+1)}+\ldots+s[j]) \,\mathrm{mod}\,m \\ &=& (h(s[0..j])-p^{j-(i-1)}\cdot h(s[0..i-1]))\,\mathrm{mod}\,m \\ &=& (H_{j+1} - p^{j+1-i}\cdot H_i) \,\mathrm{mod}\,m \end{array} \](4)
Pošto promenljive \(i\) i \(j\) uzimaju vrednosti od \(0\) do \(|s|-1\), izraz \(j+1-i\) uzima vrednosti od \(1\) do \(|s|\), te je u stvari potrebno izračunati vrednost \(p^k\) za sve vrednosti \(0\leq k \leq |s|\). Dakle, ako za datu nisku znamo heš-vrednosti svih njenih prefiksa i vrednosti \(p^k\) za \(k=0,1,\ldots,|s|\), onda na osnovu jednakosti (4) algoritmom složenosti \(O(1)\) možemo izračunati heš-vrednost proizvoljnog segmenta te niske. Heš-vrednost svih prefiksa niske \(s\) i vrednosti \(p^k \,\mathrm{mod}\,m\) za svako \(k=1,2,\ldots,|s|\) mogu se izračunati na početku rada programa i to inkrementalno, algoritmom čija je vremenska složenost \(O(|s|)\), pa je ukupna složenost računanja heš-vrednosti \(q\) različitih segmenata \(O(|s|+q)\).
Implementacija u jeziku C++ je prikazana u nastavku.
int p = 31;
long long m = 1e9 + 9;
// svi stepeni broja p
vector<long long> stepeniBrojaP(int n) {
vector<long long> pStepen(n+1);
pStepen[0] = 1;
for (int i = 1; i <= n; i++)
pStepen[i] = (pStepen[i-1] * p) % m;
return pStepen;
}
// hesevi svih prefiksa date niske
vector<long long> heseviPrefiksa(const string& s) {
int n = s.size();
vector<long long> hesPrefiksa(n+1);
hesPrefiksa[0] = 0;
for (int i = 0; i < n; i++)
hesPrefiksa[i+1] = (hesPrefiksa[i] * p + kod(s[i])) % m;
return hesPrefiksa;
}
// hes vrednost segmenta s[i..j]
// racunamo koriscenjem poznatih hes-vrednosti prefiksa i stepena broja p
long long hesSegmenta(const string& s, int i, int j,
const vector<long long>& pStepen,
const vector<long long>& hesPrefiksa) {
return
(hesPrefiksa[j+1] - (hesPrefiksa[i] * pStepen[j+1-i]) % m + m) % m;
}Primetimo da se prilikom računanja heš-vrednosti segmenta izvršava množenje heš-vrednost prefiksa odgovarajućim stepenom broja \(p\) po modulu \(m\). Da ovaj proizvod ne bi doveo do prekoračenja, potreban je uslov da \(m\cdot m\) ne izaziva prekoračenje.
Razmotrimo sada korišćenje druge predložene heš-funkcije. Tada je heš-vrednost segmenta \(s[i..j]\) jednaka:
\[\begin{eqnarray*} h'(s[i..j]) &=& (s[i]+s[i+1]\cdot p+\ldots+s[j]\cdot p^{j-i}) \,\mathrm{mod}\,m \\ &=& \left(\displaystyle\sum_{k=i}^{j}s[k]\cdot p^{k-i}\right) \,\mathrm{mod}\,m \end{eqnarray*}\]
Ako obe strane ove jednakosti pomnožimo sa \(p^{i}\) dobijamo:
\[ \begin{array}{rcl} h'(s[i..j])\cdot p^{i} &=& \left(\displaystyle\sum_{k=i}^{j}s[k]\cdot p^{k}\right) \,\mathrm{mod}\,m \\ &=& (h'(s[0..j])-h'(s[0..i-1])) \,\mathrm{mod}\,m \\ &=& (H'_{j+1} - H'_i) \,\mathrm{mod}\,m \end{array} \](5)
gde važi da je \(h'(s[0..-1]) = 0\) (što može da se desi za \(i=0\)) i gde smo niz \(H'\) definisali tako da je \(H'_0 = 0\), a \(H'_{k+1} = h'(s[0..k])\).
Primetimo da je za računanje vrednosti heš-funkcije nekog segmenta prema formuli (5) potrebno izvršiti deljenje izraza \(H'_{j+1} - H'_i\) vrednošću \(p^{i}\) po modulu \(m\). Za to je potrebno odrediti multiplikativni inverz broja \(p^{i}\) po modulu \(m\), odnosno broj \(x\) tako da važi \(p^{i}\cdot x\equiv 1 \,\mathrm{mod}\,m\), a zatim izvršiti množenje izraza \(H'_{j+1} - H'_i\) brojem \(x\). Pošto sva izračunavanja vršimo po modulu \(m\), a s obzirom na to da smo na početku pretpostavili da su brojevi \(m\) i \(p\) prosti, na osnovu male Fermaove teoreme za svaki broj \(a\) koji je uzajamno prost sa \(m\) važi \(a^{m-1}\equiv 1 \,\mathrm{mod}\,m,\) odnosno multiplikativni inverz broja \(a\) po modulu \(m\) je \(a^{m-2} \,\mathrm{mod}\,m\). Ako u ovu jednakost umesto \(a\) uvrstimo vrednost \(p^i\) (koji jeste uzajamno prost sa \(m\)), dobijamo multiplikativni inverz za proizvoljno \(p^i\) po modulu \(m\). Još efikasnije, vrednost \((p^k)^{-1}\,\mathrm{mod}\,m\) možemo izračunati kao \((p^{-1})^k\,\mathrm{mod}\,m\).
Dakle, ako su unapred poznate heš-vrednosti svih prefiksa niske \(s\) i vrednosti multiplikativnog inverza broja \(p^i, 1\leq i \leq |s|\) po modulu \(m\), izračunavanje heš-vrednosti proizvoljnog segmenta polazne niske može se na osnovu formule (5) izvršiti algoritmom složenosti \(O(1)\). Primetimo da je faza pretprocesiranja koja se sastoji od računanja heš-vrednosti svih prefiksa niske i vrednosti inverza broja \(p^i\) za svako \(i\) vremenske složenosti \(O(n\cdot \log m)\).
int p = 31;
int m = 1e9 + 9;
// racunanje inverza prostog broja p po modulu m
// koriscenjem male Fermaove teoreme
long long modInverz(int p, int m) {
return stepen_mod(p, m - 2, m);
}
// stepeni broja x po modulu m (1, ..., x^n mod m)
vector<long long> stepeniBrojaX(int x, int n, int m) {
vector<long long> xStepen(n+1);
xStepen[0] = 1;
for (int i = 1; i <= n; i++)
xStepen[i] = (xStepen[i-1] * x) % m;
return pStepen;
}
// stepeni broja p po modulu m
vector<long long> stepeniBrojaP(int n) {
return stepeniBrojaX(p, n, m);
}
// inverzi stepena broja p po modulu m
vector<long long> stepeniInverzaBrojaP(int n) {
// inverzi stepena su stepeni inverza
return stepeniBrojaX(modInverz(p, m), n, m);
}
// heseve svih prefiksa date niske s racunamo koriscenjem poznatih
// stepena broja p
vector<long long> heseviPrefiksa(const string& s,
const vector<long long>& pStepen) {
int n = s.size();
vector<long long> hesPrefiksa(n+1, 0);
for (int i = 0; i < n; i++)
hesPrefiksa[i+1] = (hesPrefiksa[i] + kod(s[i]) * pStepen[i]) % m;
}
// hes segmenta s[i..j] racunamo koriscenjem poznatih
// heseva prefiksa niske s i inverza stepena broja p
long long hesSegmenta(const string& s, int i, int j,
const vector<long long>& hesPrefiksa,
const vector<long long>& invpStepen) {
int n = s.size();
// hes vrednost segmenta racunamo preko hash vrednosti prefiksa
return
(((hesPrefiksa[j+1] - hesPrefiksa[i] + m) % m) * invpStepen[i]) % m;
}Data je niska \(s\) koja se sastoji samo od malih slova engleske abecede. Izračunati broj različitih nepraznih podniski (segmenata uzastopnih karaktera) ove niske.
Sa standardnog ulaza se učitava niska \(s\), dužine najviše \(10^5\) karaktera.
Na standardni izlaz ispisati broj različitih podniski niske \(s\).
ananas
15
a, n i s.an, na i as.ana, nan i nas.anan, nana i anas.anana i nanas.ananas.Niska ananas ima ukupno \(3+3+3+3+2+1=15\) različitih podniski.
Direktan pristup bi bio da se sve podniske ubace u skup (bilo uređen ili neuređen) i da se proveri broj elemenata tog skupa, međutim, ova ideja se može optimizovati.
Naime, dovoljno je porediti samo segmente istih dužina jer samo oni mogu biti međusobno jednaki.
Rešenje ćemo zasnovati na heširanju, pri čemu ćemo pretpostaviti da je heš-funkcija takva da je verovatnoća kolizije jako mala (tj. pretpostavićemo da različite podniske iste dužine uvek daju 1različite heš-vrednosti). Koristićemo polinomijalnu heš-funkciju \(h'(s) = (s[0]+s[1]\cdot p+\ldots+s[n-1]\cdot p^{n-1})\,\mathrm{mod}\,m\). Heš-vrednost svakog segmenta se tada može računati korišćenjem razlike heš vrednosti odgovarajućih prefiksa \(h'(s[i..j]) = (p^{-i}\cdot (H'_{j+1} - H'_i)) \,\mathrm{mod}\,m\). Umesto da računamo i poredimo tačne heš-vrednosti dva segmenta iste dužine korišćenjem modularnih multiplikativnih inverza, dovoljno je izračunati heš-vrednosti segmenata pomnožene nekim (istim) stepenom broja \(p\). Pretpostavimo da već imamo izračunate heš-vrednosti dva segmenta \(x\) i \(y\), jednog pomnoženog sa \(p^i\), a drugog sa \(p^j\). Bez narušavanja opštosti možemo pretpostaviti da je \(i<j\); da bismo dobili obe heš-vrednosti pomnožene istim stepenom broja \(p\), dovoljno je da heš-vrednost segmenta \(x\) pomnožimo sa \(p^{j-i}\).
Primer 6.4.1. Razmotrimo, na primer, segmente \(s[2..4]\) i \(s[5..7]\) dužine \(3\) niske \(s\) koja je dužine \(10\). Iz jednakosti \(p^i \cdot h'(s[i..j]) = (H'_{j+1} - H'_i) \,\mathrm{mod}\,m\):
\[\begin{eqnarray*} h_1&=&h(s[2..4])\cdot p^2=h(s[0..4])-h(s[0..1]) \,\mathrm{mod}\,m \\ h_2&=&h(s[5..7])\cdot p^5=h(s[0..7])-h(s[0..4]) \,\mathrm{mod}\,m \end{eqnarray*}\]
Umesto da računamo multiplikativne inverze brojeva \(p^2\) i \(p^5\), da bismo dobili tačne heš-vrednosti segmenata \(s[2..4]\) i \(s[5..7]\), možemo porediti vrednosti \(h_1\cdot p^{5-2}\) i \(h_2\).
Dakle, prolazićemo redom kroz sve moguće dužine \(l=1,2,\ldots, n\) segmenata niske \(s\) i konstruisati seriju heš-vrednosti svih segmenata dužine \(l\) koji su pomnoženi nekim (istim, maksimalnim) stepenom broja \(p\). Broj različitih elemenata te serije (što je, pod pretpostavkom da nema kolizija, broj različitih segmenata dužine \(l\)) možemo odrediti korišćenjem skupa (na primer, uređenog). Ukupan broj različitih segmenata jednak je zbiru broja različitih segmenata dužine \(l\) u niski, za svako moguće \(l\). Implementacija ovog pristupa u jeziku C++ je data u nastavku.
Primetimo da se u prethodnoj implementaciji prilikom računanja proizvoda heš-vrednosti segmenta i vrednosti \(p^{n-1}\) po modulu \(m\) množe dve vrednosti iz opsega \([0,m)\), te da ne bi bilo prekoračenja prilikom računanja ovog proizvoda, vrednost parametra \(m\) biramo tako da \(m\cdot m\) staje u 64-bitni ceo broj (uzeli smo najveći prost broj koji se može zapisati sa 32 bita).
Operacije za rad sa uređenim skupom od \(k\) elemenata su složenosti \(O(\log{k})\), a različitih segmenata ima ukupno \(O(n^2)\), te složenost ovog algoritma iznosi \(O(n^2\log{n})\).
Umetanjem heš-vrednosti u skup, umesto umetanja samih podniski u skup značajno je smanjena memorijska složenost skupa, koja uz heširanje iznosi \(O(n)\), a bez heširanja bi iznosila \(O(n^2)\).
Istaknimo i to da se u ovom kontekstu, kada radimo sa različitim segmentima niske, isplati uložiti dodatno vreme za računanje heš-vrednosti svih prefiksa date niske, jer ćemo izračunate heš-vrednosti veći broj puta koristiti.
int brojRazlicitihPodniski(const string &s) {
typedef unsigned long long ull;
int p = 31;
ull m = 4294967291ul; // najveci prost broj koji staje u unsigned long
int n = s.size();
// racunamo stepene broja p po modulu m
vector<ull> pStepen(n);
pStepen[0] = 1;
for (int i = 1; i < n; i++)
pStepen[i] = (pStepen[i-1] * p) % m;
// racunamo hes-vrednosti svih prefiksa date niske
vector<ull> h(n+1, 0);
for (int i = 0; i < n; i++)
h[i+1] = (h[i] + (s[i] - 'a' + 1) * pStepen[i]) % m;
// broj razlicitih podniski
int brojPodniski = 0;
// za svaku mogucu duzinu segmenta
for (int l = 1; l <= n; l++) {
// skup hes vrednosti segmenata duzine l pomnozenih sa p^{n-1}
set<ull> heseviDuzineL;
// prolazimo kroz sve segmente duzine l
for (int i = 0; i <= n - l; i++) {
// hes-vrednost segmenta racunamo
// kao razliku hes-vrednosti odgovarajucih prefiksa
ull hTekuce = (h[i+l] - h[i] + m) % m;
// racunamo hes vrednost segmenta pomnozenu sa p^{n-1} po modulu m
// tako sto je mnozimo sa p^{n-i-1}
hTekuce = (hTekuce * pStepen[n - i - 1]) % m;
// hes-vrednost dodajemo u skup,
// isti segmenti imace istu hesh vrednost pa se nece dva puta racunati
heseviDuzineL.insert(hTekuce);
}
brojPodniski += heseviDuzineL.size();
}
return brojPodniski;
}#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
using namespace std;
int brojRazlicitihPodniski(const string &s) {
typedef unsigned long long ull;
int p = 31;
ull m = 4294967291ul; // najveci prost broj koji staje u unsigned long
int n = s.size();
// racunamo stepene broja p po modulu m
vector<ull> pStepen(n);
pStepen[0] = 1;
for (int i = 1; i < n; i++)
pStepen[i] = (pStepen[i-1] * p) % m;
// racunamo hes-vrednosti svih prefiksa date niske
vector<ull> h(n+1, 0);
for (int i = 0; i < n; i++)
h[i+1] = (h[i] + (s[i] - 'a' + 1) * pStepen[i]) % m;
// broj razlicitih podniski
int brojPodniski = 0;
// za svaku mogucu duzinu segmenta
for (int l = 1; l <= n; l++) {
// skup hes vrednosti segmenata duzine l pomnozenih sa p^{n-1}
set<ull> heseviDuzineL;
// prolazimo kroz sve segmente duzine l
for (int i = 0; i <= n - l; i++) {
// hes-vrednost segmenta racunamo
// kao razliku hes-vrednosti odgovarajucih prefiksa
ull hTekuce = (h[i+l] - h[i] + m) % m;
// racunamo hes vrednost segmenta pomnozenu sa p^{n-1} po modulu m
// tako sto je mnozimo sa p^{n-i-1}
hTekuce = (hTekuce * pStepen[n - i - 1]) % m;
// hes-vrednost dodajemo u skup,
// isti segmenti imace istu hesh vrednost pa se nece dva puta racunati
heseviDuzineL.insert(hTekuce);
}
brojPodniski += heseviDuzineL.size();
}
return brojPodniski;
}
int main() {
string s;
cin >> s;
cout << brojRazlicitihPodniski(s) << endl;
return 0;
}Napisati program koji određuje leksikografski najmanju rotaciju date niske.
Sa standardnog ulaza se unosi niska dužine najviše \(10^6\) karaktera.
Na standardni izlaz ispisati leksikografski najmanju nisku koja se dobija rotiranjem karaktera unete niske.
atlas
asatl
Rotacije niske atlas su atlas, tlasa, lasat, asatl i satla. Leksikografski najmanja niska od njih je asatl.
Do rešenja možemo doći tako što ćemo određivati jednu po jednu rotaciju niske i porediti ih leksikografski sa do tada najmanjom. Ako leksikografsko poređenje vršimo direktim algoritmom, čija je složenost \(O(n)\) u najgorem slučaju, dobija se algoritam složenosti \(O(n^2)\) (doduše, ako su niske nasumično generisane ili sadrže tekst na prirodnom jeziku, leksikografski redosled se može odrediti već nakon analize prvih nekoliko karaktera, pa će algoritam raditi efikasnije). Da bi se izbeglo građenje novih niski (što je skupa operacija usled alokacije memorije), rotacije možemo dobiti tako što analiziramo sve podniske dužine \(n\) niske \(ss\) koja se dobija tako što se nadovezivanjem učitane niska \(s\) dva puta.
Leksikografsko poređenje se može ubrzati korišćenjem heširanja. Pretpostavimo, jednostavnosti radi, da neće biti kolizija. Leksikografski redosled niski se određuje tako što se pronađe prvi karakter koji se razlikuje, tj. tako što se pronađe najduži zajednički prefiks dve niske koje se porede. On se može pronaći binarnom pretragom. U svakom koraku se ispituje jednakost nekih prefiksa dve niske koje se porede. Pošto su oni segmenti niske \(ss\), poređenje možemo izvršiti tako što izračunamo njihove heš-vrednosti (kao heš-vrednosti segmenata niske \(ss\)) i uporedimo ih. Implementacija je olakšana, jer su niske koje se porede iste dužine. Kada se nađe dužina najdužeg zajedničkog prefiksa, poredi se naredni karakter (osim u slučaju kada su niske jednake, što se lako prepoznaje jer je tada dužina zajedničkog prefiksa jednaka dužini niski koje se porede).
Pošto se binarna pretraga vrši u vremenu \(\log{n}\), a rotacija postoji \(n\), složenost najgoreg slučaja ovog algoritma je \(n\log{n}\).
// znajuci heseve H svih prefiksa niske i stepene broja P
// izracunavamo najduzi zajednicki prefiks podniski na pozicijama
// [i1, i1+n) i [i2, i2+n)
int najduziZajednickiPrefiks(const vector<long long>& H,
const vector<long long>& P,
int i1, int i2, int n) {
// binarna pretraga
int l = 0, d = n-1;
while (l <= d) {
int m = l + (d - l) / 2;
// poredimo da li se prefiksi niski dužine m poklapaju
// pretpostavljamo da nema kolizija
if (hesSegmenta(H, P, i1, i1+m) == hesSegmenta(H, P, i2, i2+m))
l = m + 1;
else
d = m - 1;
}
return l;
}
bool leksikgrafskiManjaNiska(const vector<long long>& H,
const vector<long long>& P,
int i1, int i2, int n,
const string& ss) {
int k = najduziZajednickiPrefiks(H, P, i1, i2, n);
return k < n && ss[i1 + k] < ss[i2 + k];
}
string leksikografskiNajmanjaRotacija(const string& s) {
int n = s.length();
string ss = s + s;
vector<long long> H = heseviPrefiksa(ss);
vector<long long> P = stepeniBrojaP(n);
int iMin = 0;
for (int i = 1; i + n < ss.length(); i++)
if (leksikgrafskiManjaNiska(H, P, i, iMin, n, ss))
iMin = i;
return ss.substr(iMin, n);
}#include <iostream>
#include <string>
#include <vector>
using namespace std;
int p = 31;
long long m = 1e9 + 9;
// svi stepeni broja p
vector<long long> stepeniBrojaP(int n) {
vector<long long> pStepen(n+1);
pStepen[0] = 1;
for (int i = 1; i <= n; i++)
pStepen[i] = (pStepen[i-1] * p) % m;
return pStepen;
}
// hesevi svih prefiksa date niske
vector<long long> heseviPrefiksa(const string& s) {
int n = s.size();
vector<long long> hesPrefiksa(n+1);
hesPrefiksa[0] = 0;
for (int i = 0; i < n; i++)
hesPrefiksa[i+1] = (hesPrefiksa[i] * p + (s[i] - 'a' + 1)) % m;
return hesPrefiksa;
}
long long hesSegmenta(const vector<long long>& H,
const vector<long long>& p,
int i, int j) {
return (H[j+1] - p[j+1-i]*H[i] % m + m) % m;
}
// znajuci heseve H svih prefiksa niske i stepene broja P
// izracunavamo najduzi zajednicki prefiks podniski na pozicijama
// [i1, i1+n) i [i2, i2+n)
int najduziZajednickiPrefiks(const vector<long long>& H,
const vector<long long>& P,
int i1, int i2, int n) {
// binarna pretraga
int l = 0, d = n-1;
while (l <= d) {
int m = l + (d - l) / 2;
// poredimo da li se prefiksi niski dužine m poklapaju
// pretpostavljamo da nema kolizija
if (hesSegmenta(H, P, i1, i1+m) == hesSegmenta(H, P, i2, i2+m))
l = m + 1;
else
d = m - 1;
}
return l;
}
bool leksikgrafskiManjaNiska(const vector<long long>& H,
const vector<long long>& P,
int i1, int i2, int n,
const string& ss) {
int k = najduziZajednickiPrefiks(H, P, i1, i2, n);
return k < n && ss[i1 + k] < ss[i2 + k];
}
string leksikografskiNajmanjaRotacija(const string& s) {
int n = s.length();
string ss = s + s;
vector<long long> H = heseviPrefiksa(ss);
vector<long long> P = stepeniBrojaP(n);
int iMin = 0;
for (int i = 1; i + n < ss.length(); i++)
if (leksikgrafskiManjaNiska(H, P, i, iMin, n, ss))
iMin = i;
return ss.substr(iMin, n);
}
int main() {
ios_base::sync_with_stdio(false);
string s;
cin >> s;
cout << leksikografskiNajmanjaRotacija(s) << endl;
return 0;
}Poslednji od pomenutih scenarija poznat je pod nazivom rođendanski paradoks (engl. birthday paradox) i odnosi se na sledeći kontekst: ako se u jednoj sobi nalazi \(n\) osoba, verovatnoća da neke dve osobe imaju rođendan istog dana za \(n=23\) iznosi oko \(50\%\), dok za \(n=70\) ona iznosi čak \(99.9\%\).↩︎