Szczegółowe omówienie zadania Subwords które jest ilustracją algorytmu liczenia hashy (skrótów)
–
Zadanie Subwords pokazuje jak wykorzystać algorytm liczenia hashy (skrótów) w konkursach informatycznych a także jego potężna zastosowania:
https://tiny.pl/7hl83
https://tiny.pl/7hl83
——-
Kod C++ programu Subwords, który jest omówiony w powyższym filmie i który otrzymuje 100%
–
#include <bits/stdc++.h>
using namespace std;
const int MAKS_DLUGOSC_SLOWA = 1e3+7; //1007
const int MAKS_PDOSLOW = MAKS_DLUGOSC_SLOWA*MAKS_DLUGOSC_SLOWA;
const long long int MODULO1 = 1e9+7; //1000000007
const long long int MODULO2 = 1e9+9; //1000000009
const long long int g1 = 59;
const long long int g2 = 313;
string slowo;
long long int potegi1[MAKS_DLUGOSC_SLOWA];
long long int potegi2[MAKS_DLUGOSC_SLOWA];
long long int hash1_slowo[MAKS_DLUGOSC_SLOWA];
long long int hash2_slowo[MAKS_DLUGOSC_SLOWA];
pair < long long int, long long int> hashe_podslow[MAKS_PDOSLOW];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int liczba_roznych_podslow, ile_hashy_podslow;
long long int wartosc_hasha, zmiana, hash1_podslowa, hash2_podslowa;
int indeks_potega_wyrownujaca;
int poczatek, koniec;
int i,j;
cin >> slowo;
slowo = "#" + slowo;
//tablica 59^0 59^1 59^2 ...
potegi1[0] = 1;
for (i=1; i<slowo.length(); ++i) {
potegi1[i] = potegi1[i-1]*g1;
potegi1[i] %= MODULO1;
}
//tablica 313^0 313^1 313^2 ...
potegi2[0] = 1;
for (i=1; i<slowo.length(); ++i) {
potegi2[i] = potegi2[i-1]*g2;
potegi2[i] %= MODULO2;
}
//hashe numer 1 od pocztku do danej litery
hash1_slowo[0] = (long long int)slowo[0];
for (i=1; i<slowo.length(); ++i) {
hash1_slowo[i] = hash1_slowo[i-1];
zmiana = (long long int)slowo[i] * potegi1[i];
zmiana %= MODULO1;
hash1_slowo[i] += zmiana;
hash1_slowo[i] %= MODULO1;
}
//hashe numer 2 od pocztku do danej litery
hash2_slowo[0] = (long long int)slowo[0];
for (i=1; i<slowo.length(); ++i) {
hash2_slowo[i] = hash2_slowo[i-1];
zmiana = (long long int)slowo[i] * potegi2[i];
zmiana %= MODULO2;
hash2_slowo[i] += zmiana;
hash2_slowo[i] %= MODULO2;
}
//liczymy podwjne hashe kadego podsowa
ile_hashy_podslow = 0;
for (poczatek=1; poczatek<slowo.length(); ++poczatek) {
for (koniec=poczatek; koniec<slowo.length(); ++koniec) {
indeks_potega_wyrownujaca = slowo.length() - 1 - (koniec-poczatek) - poczatek;
//liczymy #1 podsowa
hash1_podslowa = hash1_slowo[koniec] - hash1_slowo[poczatek-1];
hash1_podslowa += MODULO1;
hash1_podslowa %= MODULO1;
hash1_podslowa *= potegi1[indeks_potega_wyrownujaca];
hash1_podslowa %= MODULO1;
//liczymy #2 podsowa
hash2_podslowa = hash2_slowo[koniec] - hash2_slowo[poczatek-1];
hash2_podslowa += MODULO2;
hash2_podslowa %= MODULO2;
hash2_podslowa *= potegi2[indeks_potega_wyrownujaca];
hash2_podslowa %= MODULO2;
//hash podsowa to #1 oraz #2 - czyli para hashy
hashe_podslow[ile_hashy_podslow] = make_pair(hash1_podslowa,hash2_podslowa);
++ile_hashy_podslow;
}
}
//sortujemy wszystkie hashe podsw
sort ( hashe_podslow, hashe_podslow+ile_hashy_podslow) ;
//liczymy ile jest rnych hashy - rnych podsw
liczba_roznych_podslow = 1;
for (i=1; i<ile_hashy_podslow; ++i) {
if (hashe_podslow[i-1] != hashe_podslow[i])
++liczba_roznych_podslow; //jeli para hashy jest rna od poprzedniej (w posorotwanej tablicy) to mamy nowe podsowo
}
//wystarczy wypisa wynik
cout << liczba_roznych_podslow << "\n";
return 0;
}
————————
————————
————————
Kod C++ programu Subwords, który wykorzystuje pojedynczy hash i który otrzymuje 65% z uwagi na kolizje hashy:
#include <bits/stdc++.h>
using namespace std;
const int MAKS_DLUGOSC_SLOWA = 1e3+7; //1007
const int MAKS_PDOSLOW = MAKS_DLUGOSC_SLOWA*MAKS_DLUGOSC_SLOWA;
const long long int MODULO1 = 1e9+7; //1000000007
const long long int g1 = 59;
string slowo;
long long int potegi1[MAKS_DLUGOSC_SLOWA];
long long int hash1_slowo[MAKS_DLUGOSC_SLOWA];
long long int hashe_podslow[MAKS_PDOSLOW];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int liczba_roznych_podslow, ile_hashy_podslow;
long long int wartosc_hasha, zmiana, hash1_podslowa, hash2_podslowa;
int indeks_potega_wyrownujaca;
int poczatek, koniec;
int i,j;
cin >> slowo;
slowo = "#" + slowo;
//tablica 59^0 59^1 59^2 ...
potegi1[0] = 1;
for (i=1; i<slowo.length(); ++i) {
potegi1[i] = potegi1[i-1]*g1;
potegi1[i] %= MODULO1;
}
//hashe numer 1 od początku do danej litery
hash1_slowo[0] = (long long int)slowo[0];
for (i=1; i<slowo.length(); ++i) {
hash1_slowo[i] = hash1_slowo[i-1];
zmiana = (long long int)slowo[i] * potegi1[i];
zmiana %= MODULO1;
hash1_slowo[i] += zmiana;
hash1_slowo[i] %= MODULO1;
}
//liczymy pojedyncze hashe każdego podsłowa
ile_hashy_podslow = 0;
for (poczatek=1; poczatek<slowo.length(); ++poczatek) {
for (koniec=poczatek; koniec<slowo.length(); ++koniec) {
indeks_potega_wyrownujaca = slowo.length() - 1 - (koniec-poczatek) - poczatek;
//liczymy hash podsłowa
hash1_podslowa = hash1_slowo[koniec] - hash1_slowo[poczatek-1];
hash1_podslowa += MODULO1;
hash1_podslowa %= MODULO1;
hash1_podslowa *= potegi1[indeks_potega_wyrownujaca];
hash1_podslowa %= MODULO1;
//hashe wszystkich podsłów trzymamy w tablicy
hashe_podslow[ile_hashy_podslow] = hash1_podslowa;
++ile_hashy_podslow;
}
}
//sortujemy wszystkie hashe podsłów
sort (hashe_podslow, hashe_podslow+ile_hashy_podslow) ;
//liczymy ile jest różnych hashy - różnych podsłów
liczba_roznych_podslow = 1;
for (i=1; i<ile_hashy_podslow; ++i) {
if (hashe_podslow[i-1] != hashe_podslow[i])
++liczba_roznych_podslow; //jeśli aktualny hash różny od poprzedniego (w posorotwanej tablicy) to mamy nowe podsłowo
}
//wystarczy wypisać wynik
cout << liczba_roznych_podslow << "\n";
return 0;
}